โจทย์
ให้ยกกำลังสองจำนวนนั้น แล้วแบ่งเลขโดดฐานสิบของผลลัพธ์ออกเป็นสองส่วน ส่วนขวา คือเลขโดด d หลักสุดท้าย โดย d คือจำนวนหลักของจำนวนเดิม และ ส่วนซ้าย คือเลขโดดที่เหลือ (เป็น 0 ถ้าไม่เหลืออะไร) จำนวนนั้นเป็น จำนวนคาเปรการ์ (Kaprekar number) ถ้าส่วนขวาไม่เป็นศูนย์และทั้งสองส่วนบวกกันได้จำนวนเดิม เช่น 297 มี 3 หลัก และ 297² = 88209 ส่วนขวาคือ 209 ส่วนซ้ายคือ 88 และ 88 + 209 = 297
จงเขียน kaprekar_number(n)
แต่ละแหล่งข้อมูลนิยามไม่ตรงกัน ในโจทย์นี้จะแบ่งที่ตำแหน่ง d หลักจากทางขวาเสมอ (ตรงกับรายการใน OEIS A053816 และกรณี p = d ของนิยามใน Wikipedia) บางแหล่งยอมให้ลองแบ่งที่ตำแหน่งอื่นด้วย ซึ่งจะทำให้จำนวนอย่าง 4879 ผ่าน ทั้งที่นิยามในโจทย์นี้ไม่ยอมรับ ส่วนขวาอาจขึ้นต้นด้วยเลขศูนย์ได้ (สำหรับ 703 จะได้ 703² = 494209 แบ่งเป็น 494 กับ 209) และต้องไม่เป็นศูนย์ ดังนั้น 10, 100, ... ไม่ใช่จำนวนคาเปรการ์ ส่วน 1 เป็นจำนวนคาเปรการ์ เพราะ 1² = 1 ได้ส่วนซ้ายเป็น 0 และส่วนขวาเป็น 1
อินพุต
n: จำนวนที่ต้องการตรวจสอบ
เอาต์พุต
คืนค่า true ถ้า n เป็นจำนวนคาเปรการ์ตามนิยามข้างต้น มิฉะนั้นคืนค่า false
เงื่อนไข
1 ≤ n ≤ 10^9
ตัวอย่าง
อินพุต:
n = 45
ผลลัพธ์ที่คาดหวัง:
expected = True
อินพุต:
long long n = 45;
ผลลัพธ์ที่คาดหวัง:
bool expected = true;
อินพุต:
long n = 45;
ผลลัพธ์ที่คาดหวัง:
bool expected = true;
คำอธิบาย
45 มี 2 หลัก และ 45² = 2025 ส่วนซ้ายคือ 20 ส่วนขวาคือ 25 และ 20 + 25 = 45 คำตอบจึงเป็น true
อินพุต:
n = 4879
ผลลัพธ์ที่คาดหวัง:
expected = False
อินพุต:
long long n = 4879;
ผลลัพธ์ที่คาดหวัง:
bool expected = false;
อินพุต:
long n = 4879;
ผลลัพธ์ที่คาดหวัง:
bool expected = false;
คำอธิบาย
4879 มี 4 หลัก และ 4879² = 23804641 ส่วนซ้ายคือ 2380 ส่วนขวาคือ 4641 และ 2380 + 4641 = 7021 ไม่ใช่ 4879 คำตอบจึงเป็น false
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
ให้ d เป็นจำนวนหลักของ n และคำนวณ n² ด้วยจำนวนเต็ม 64 บิต
คำใบ้ 2
ให้ p = 10^d ส่วนขวาคือ n² mod p และส่วนซ้ายคือ n² / p
คำใบ้ 3
ถ้าส่วนขวาเป็น 0 ให้ตอบว่าไม่ใช่ แม้ผลบวกจะตรงกันก็ตาม
ความซับซ้อนที่คาดหวัง
เวลา O(d) เมื่อมี d หลัก, หน่วยความจำเพิ่ม O(1)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน