โจทย์
แต่ละจำนวนให้มาเป็นสตริงของเลขโดดฐานสิบ และยาวได้ถึง 60 หลัก ซึ่งเกินกว่าที่จำนวนเต็ม 64 บิตจะเก็บได้ไปมาก ให้บวกทุกจำนวนเข้าด้วยกันแล้วคืนค่าผลรวมที่ถูกต้องทุกหลัก วิธีที่ใช้ก็คือการบวกแบบตั้งหลักที่เรียนกันในโรงเรียน คือบวกเลขโดดจากขวาไปซ้ายแล้วทดไปยังหลักถัดไป
จงเขียนฟังก์ชัน sum_of_big_numbers(numbers)
อินพุต
numbers: จำนวนเต็มที่ไม่เป็นลบซึ่งเขียนเป็นสตริงของเลขโดด ไม่มีเลขศูนย์นำหน้า (ศูนย์เขียนเป็น "0")
เอาต์พุต
คืนค่าผลรวมที่แน่นอนเป็นสตริงของเลขโดดที่ไม่มีเลขศูนย์นำหน้า ถ้ารายการว่าง ผลรวมคือ "0"
เงื่อนไข
0 ≤ numbers.length ≤ 100; แต่ละจำนวนมี 1 ถึง 60 หลัก
ตัวอย่าง
อินพุต:
numbers = ["999", "1"]
ผลลัพธ์ที่คาดหวัง:
expected = "1000"
อินพุต:
std::vector<std::string> numbers = {"999", "1"};
ผลลัพธ์ที่คาดหวัง:
std::string expected = "1000";
อินพุต:
string[] numbers = new string[] {"999", "1"};
ผลลัพธ์ที่คาดหวัง:
string expected = "1000";
คำอธิบาย
การบวก 1 เข้ากับ 999 ต้องทดต่อกันไปทุกหลัก จึงได้ "1000"
อินพุต:
numbers = ["98765432109876543210", "12345678901234567890"]
ผลลัพธ์ที่คาดหวัง:
expected = "111111111011111111100"
อินพุต:
std::vector<std::string> numbers = {"98765432109876543210", "12345678901234567890"};
ผลลัพธ์ที่คาดหวัง:
std::string expected = "111111111011111111100";
อินพุต:
string[] numbers = new string[] {"98765432109876543210", "12345678901234567890"};
ผลลัพธ์ที่คาดหวัง:
string expected = "111111111011111111100";
คำอธิบาย
เมื่อบวกทีละหลัก จำนวน 20 หลักทั้งสองให้ผลเป็น "111111111011111111100" ซึ่งยาวกว่าแต่ละจำนวนหนึ่งหลัก
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
จัดตัวเลขให้หลักสุดท้ายตรงกัน
คำใบ้ 2
บวกทีละหลัก โดยเก็บตัวทดไว้สำหรับหลักถัดไป
คำใบ้ 3
เมื่อบวกครบทุกหลักแล้ว ตัวทดที่เหลือจะกลายเป็นเลขโดดนำหน้าตัวใหม่
ความซับซ้อนที่คาดหวัง
เวลา O(total digits), หน่วยความจำเพิ่ม O(max length)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน