Count Iterations When Multiplying by Two
Solve this ProblemEasy10 min
Topics
BasicsComplexityMath
Companies
TCSInfosysWipro
For the loop
i = 1; while (i < n) { i *= 2; }, return how many times it runs.
Multiplying the loop variable is the mirror image of dividing it: instead of shrinking n towards 1, it grows i towards n, doublingExponential Growth of the Loop VariableBecause i doubles each pass, it reaches n after only about log₂(n) passes. each time. Either way the loop runs about log₂(n) times, so loops like for (i = 1; i < n; i *= 2) are O(log n).
Test Case 1:
Input:n = 10
Output:4
Explanation:i goes 1 → 2 → 4 → 8 → 16; after four doublings it is no longer below 10.
Test Case 2:
Input:n = 16
Output:4
Explanation:i reaches 16 after four doublings, and 16 < 16 is false.
Constraints
- ◆
1 ≤ n ≤ 1000000000
Try the Dry Run
Approach & Solutions
Run the Doubling LoopGood
Start i at 1 and double it while it is still below n, counting the passes. i grows 1, 2, 4, 8, … so it passes n after about log₂(n) steps — the mirror image of a halving loop. For n up to a billion, i stays within the int range (at most 2³⁰).
Time
O(log n)Space
O(1)Java
class Solution {
public int doublingLoopCount(int n) {
int i = 1;
int count = 0;
while (i < n) {
i *= 2;
count++;
}
return count;
}
}Bit Length of n − 1Optimal
The loop stops at the first power of two that is ≥ n, so the answer is ⌈log₂ n⌉. For n ≥ 2 that equals the number of binary digits of n − 1: 32 minus the leading zero bits of n − 1, or bit_length() in Python. n = 1 is handled first, because the loop never runs then.
Time
O(1)Space
O(1)Java
class Solution {
public int doublingLoopCount(int n) {
if (n <= 1) {
return 0;
}
return 32 - Integer.numberOfLeadingZeros(n - 1);
}
}