โจทย์
รากที่สองแบบจำนวนเต็มของ n คือรากที่สองที่ปัดเศษลง หรือก็คือจำนวนเต็ม r ที่มากที่สุดซึ่ง r × r ≤ n ฟังก์ชันหารากที่สองในไลบรารีทำงานกับจำนวนทศนิยมแบบ floating point จึงอาจคลาดเคลื่อนไป 1 เมื่ออินพุตมีค่ามาก ดังนั้นให้คำนวณด้วยจำนวนเต็มล้วน ๆ เช่น ใช้การค้นหาแบบทวิภาค (binary search) บนช่วงของคำตอบที่เป็นไปได้
จงเขียนฟังก์ชัน integer_square_root(n)
อินพุต
n: จำนวนเต็มที่ไม่เป็นลบ
เอาต์พุต
คืนค่าจำนวนเต็ม r ที่มากที่สุดซึ่ง r × r ≤ n
เงื่อนไข
0 ≤ n ≤ 10^18
ตัวอย่าง
อินพุต:
n = 50
ผลลัพธ์ที่คาดหวัง:
expected = 7
อินพุต:
long long n = 50;
ผลลัพธ์ที่คาดหวัง:
long long expected = 7;
อินพุต:
long n = 50;
ผลลัพธ์ที่คาดหวัง:
long expected = 7;
คำอธิบาย
7 × 7 = 49 ≤ 50 แต่ 8 × 8 = 64 > 50 คำตอบจึงเป็น 7
อินพุต:
n = 144
ผลลัพธ์ที่คาดหวัง:
expected = 12
อินพุต:
long long n = 144;
ผลลัพธ์ที่คาดหวัง:
long long expected = 12;
อินพุต:
long n = 144;
ผลลัพธ์ที่คาดหวัง:
long expected = 12;
คำอธิบาย
144 เท่ากับ 12 × 12 พอดี คำตอบจึงเป็น 12
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
คำตอบอยู่ระหว่าง 0 ถึง n และ r × r เพิ่มขึ้นเมื่อ r เพิ่มขึ้น จึงลดช่วงลงครึ่งหนึ่งได้ทุกขั้น
คำใบ้ 2
เมื่อ n มีค่ามาก r × r อาจล้นได้ ให้เปรียบเทียบ r กับ n / r แทน หรือจำกัดขอบบนไว้
คำใบ้ 3
ลองคำนวณอินพุตเล็ก ๆ อย่าง 0, 1 และ 3 ด้วยมือดู
ความซับซ้อนที่คาดหวัง
เวลา O(log n), หน่วยความจำเพิ่ม O(1)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน