โจทย์ทั้งหมด
ปานกลาง 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

จำนวนคาเปรการ์ (Kaprekar Number)

ตรวจสอบว่ากำลังสองของจำนวน d หลัก แบ่งเป็นส่วนซ้ายกับส่วนขวาที่ยาว d หลักแล้วบวกกันได้ตัวมันเองหรือไม่

สิ่งที่คุณจะได้เรียนรู้

  • แบ่งจำนวนเป็นส่วนซ้ายกับส่วนขวาที่ตำแหน่งหลักที่กำหนด
  • ใช้จำนวนหลักของ n เลือกตำแหน่งที่แบ่ง
  • ตรวจทุกเงื่อนไขของนิยาม รวมถึงข้อที่ห้ามเป็นศูนย์

โจทย์

ให้ยกกำลังสองจำนวนนั้น แล้วแบ่งเลขโดดฐานสิบของผลลัพธ์ออกเป็นสองส่วน ส่วนขวา คือเลขโดด 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

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
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

ตัวอย่างที่ 2
อินพุต:
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 กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก