Count How Many Times N Can Be Halved
Solve this ProblemEasy10 min
Topics
BasicsComplexityMath
Companies
TCSInfosysWipro
Given a positive integer
n, return how many times it can be halved (with integer division) before it becomes 1.
The answer is ⌊log₂ n⌋, and the halving loop is the classic O(log n)Logarithmic Time O(log n)Work that grows by one step each time the input doubles, because every step cuts the problem in half. pattern: every step throws away half of what is left, so doubling the input adds just one more step. Binary search works the same way, which is why it can search a billion items in about 30 comparisons.
Test Case 1:
Input:n = 20
Output:4
Explanation:20 → 10 → 5 → 2 → 1 (integer halving): four halvings.
Test Case 2:
Input:n = 1
Output:0
Explanation:Already 1, so no halving is needed.
Constraints
- ◆
1 ≤ n ≤ 1000000000
Try the Dry Run
Approach & Solutions
Halve Until 1Good
Keep dividing n by 2 (integer division) and count the steps until it reaches 1. Each step cuts the remaining number in half, so even a billion needs only about 30 steps — this is what logarithmic time looks like.
Time
O(log n)Space
O(1)Java
class Solution {
public int halvings(int n) {
int count = 0;
while (n > 1) {
n /= 2;
count++;
}
return count;
}
}Position of the Highest 1 BitOptimal
Halving with integer division is the same as shifting the binary digits right by one. So the answer is the position of n's highest 1 bit, counted from 0. Built-ins give it directly: 31 − (leading zero bits) in Java, C, C++ and JavaScript, or bit_length() − 1 in Python.
Time
O(1)Space
O(1)Java
class Solution {
public int halvings(int n) {
return 31 - Integer.numberOfLeadingZeros(n);
}
}