โจทย์
ในเลขฐาน b จะเขียนจำนวนด้วยเลขโดด 0 ถึง b − 1 โดยตัวอักษร A ถึง Z แทนค่าเลขโดด 10 ถึง 35 ดังนั้น FF ในฐาน 16 คือ 255 ซึ่งเท่ากับ 377 ในฐาน 8 และ 11111111 ในฐาน 2 ให้แปลง digits ซึ่งเขียนในฐาน from_base ไปเป็นจำนวนเดียวกันที่เขียนในฐาน to_base
จงเขียนฟังก์ชัน base_converter(digits, from_base, to_base)
อินพุต
digits: จำนวนในฐาน from_base เป็นสตริงที่ไม่ว่าง ประกอบด้วยเลขโดดและตัวอักษรพิมพ์ใหญ่ ซึ่งแต่ละตัวมีค่าน้อยกว่า from_base และอาจมีเลขศูนย์นำหน้า
from_base: ฐานของอินพุต
to_base: ฐานของผลลัพธ์
เอาต์พุต
คืนค่าจำนวนในฐาน to_base โดยใช้ 0-9 และตัวพิมพ์ใหญ่ A-Z และไม่มีเลขศูนย์นำหน้า ถ้าค่าเป็นศูนย์ให้คืนค่า "0"
เงื่อนไข
2 ≤ from_base, to_base ≤ 36
ค่าของจำนวนไม่เกิน 10^18
ตัวอย่าง
อินพุต:
digits = "FF"
from_base = 16
to_base = 8
ผลลัพธ์ที่คาดหวัง:
expected = "377"
อินพุต:
std::string digits = "FF";
long long from_base = 16;
long long to_base = 8;
ผลลัพธ์ที่คาดหวัง:
std::string expected = "377";
อินพุต:
string digits = "FF";
long from_base = 16;
long to_base = 8;
ผลลัพธ์ที่คาดหวัง:
string expected = "377";
คำอธิบาย
FF คือ 15 × 16 + 15 = 255 และ 255 = 3 × 64 + 7 × 8 + 7 คำตอบจึงเป็น "377"
อินพุต:
digits = "1010"
from_base = 2
to_base = 36
ผลลัพธ์ที่คาดหวัง:
expected = "A"
อินพุต:
std::string digits = "1010";
long long from_base = 2;
long long to_base = 36;
ผลลัพธ์ที่คาดหวัง:
std::string expected = "A";
อินพุต:
string digits = "1010";
long from_base = 2;
long to_base = 36;
ผลลัพธ์ที่คาดหวัง:
string expected = "A";
คำอธิบาย
1010 ในเลขฐานสองคือ 10 ซึ่งในฐาน 36 เขียนเป็นเลขโดดตัวเดียวคือ "A"
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
ไล่อ่านอินพุตจากซ้ายไปขวา โดยคูณค่าสะสมด้วย from_base แล้วบวกเลขโดดแต่ละตัว
คำใบ้ 2
เมื่อจะเขียนผลลัพธ์ ให้เก็บเศษจากการหารด้วย to_base ซึ่งจะได้เลขโดดตัวท้ายสุดออกมาก่อน
คำใบ้ 3
จัดการค่าศูนย์เป็นกรณีพิเศษ เพื่อให้ผลลัพธ์เป็น "0" ไม่ใช่สตริงว่าง
ความซับซ้อนที่คาดหวัง
เวลา O(L), หน่วยความจำเพิ่ม O(L) โดย L คือจำนวนหลัก
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน