Count Iterations When Dividing by K
Solve this ProblemEasy10 min
Topics
BasicsComplexityMath
Companies
TCSInfosysWipro
For the loop
while (n > 0) { n /= k; }, return how many times it runs for the given n and k.
A loop whose variable is divided by a constant each time is logarithmicLogarithmic LoopA loop whose variable is multiplied or divided by a constant each pass, so it runs about log(n) times.: the number of passes is the number of digits of n in base k, roughly log_k(n). The base only changes a constant factor (log₁₀ n vs log₂ n), so all such loops are simply O(log n).
Test Case 1:
Input:n = 1000, k = 10
Output:4
Explanation:1000 → 100 → 10 → 1 → 0: four divisions — the number of decimal digits of 1000.
Test Case 2:
Input:n = 8, k = 2
Output:4
Explanation:8 → 4 → 2 → 1 → 0. In binary 8 is 1000, four digits.
Constraints
- ◆
1 ≤ n ≤ 1000000000 - ◆
2 ≤ k ≤ 10
Try the Dry Run
Approach & Solutions
Divide Until ZeroOptimal
Run "while (n > 0) { n /= k; count++; }" and count the passes. Each division shrinks n by a factor of k, so the loop runs about log_k(n) times — one pass per digit of n written in base k. A billion needs only 10 passes in base 10, or 30 in base 2.
Time
O(log n)Space
O(1)Java
class Solution {
public int divisionLoopCount(int n, int k) {
int count = 0;
while (n > 0) {
n /= k;
count++;
}
return count;
}
}Grow a Power of K InsteadGood
Count upward instead of dividing down: start with power = 1 and multiply it by k until it exceeds n. The number of multiplications is the same as the number of divisions above — both measure how many base-k digits n has. A 64-bit variable is used because power can overshoot the int range just before it passes n.
Time
O(log n)Space
O(1)Java
class Solution {
public int divisionLoopCount(int n, int k) {
long power = 1;
int count = 0;
while (power <= n) {
power *= k;
count++;
}
return count;
}
}