โจทย์
Repeatedly divide n by 2, dropping any remainder (integer division), until it becomes 1. Count how many divisions that takes.
Implement halve_until_one(n).
Input
n: A positive integer.
Output
Return the number of divisions.
เงื่อนไข
1 ≤ n ≤ 1,000,000,000,000
ตัวอย่าง
ตัวอย่างที่ 1
อินพุต:
n = 20
ผลลัพธ์ที่คาดหวัง:
expected = 4อินพุต:
long long n = 20;
ผลลัพธ์ที่คาดหวัง:
long long expected = 4;อินพุต:
long n = 20;
ผลลัพธ์ที่คาดหวัง:
long expected = 4;คำอธิบาย
20 → 10 → 5 → 2 → 1 takes 4 divisions.
ตัวอย่างที่ 2
อินพุต:
n = 1
ผลลัพธ์ที่คาดหวัง:
expected = 0อินพุต:
long long n = 1;
ผลลัพธ์ที่คาดหวัง:
long long expected = 0;อินพุต:
long n = 1;
ผลลัพธ์ที่คาดหวัง:
long expected = 0;คำอธิบาย
n is already 1, so no divisions are needed.
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
Count how many times you can shrink the number by dividing by two before it becomes one.
คำใบ้ 2
Repeated integer division is enough here; no need to track the discarded remainders.
คำใบ้ 3
Make sure you stop exactly when the value reaches one, not when it becomes zero.
ความซับซ้อนที่คาดหวัง
O(log n) time, O(1) extra space
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน