Count Iterations of a Stepping Loop
Solve this ProblemEasy5 min
Topics
BasicsComplexity
Companies
TCSInfosysWipro
For the loop
for (i = 0; i < n; i += k), return how many times its body runs.
Finding a loop's complexity starts with counting its iterationsIterationOne pass through a loop body.. Here i starts at 0 and jumps by k, so the body runs about n / k times — exactly ⌈n / k⌉. When k is a fixed constant this is O(n); the step size changes the count by a constant factor, not the growth rate.
Test Case 1:
Input:n = 10, k = 3
Output:4
Explanation:i takes the values 0, 3, 6 and 9 before reaching 12, which fails i < 10.
Test Case 2:
Input:n = 0, k = 5
Output:0
Explanation:The condition 0 < 0 is false immediately.
Constraints
- ◆
0 ≤ n ≤ 1000000 - ◆
1 ≤ k ≤ 1000000
Try the Dry Run
Approach & Solutions
Run the Loop and CountGood
Simply run "for (i = 0; i < n; i += k)" and count its passes. Because i jumps by k each time, there are about n / k passes — the loop is O(n / k), which is O(n) when k is a fixed constant.
Time
O(n / k)Space
O(1)Java
class Solution {
public int stepLoopCount(int n, int k) {
int count = 0;
for (int i = 0; i < n; i += k) {
count++;
}
return count;
}
}Ceiling Division FormulaOptimal
The passes are i = 0, k, 2k, … while i < n, so their number is n / k rounded up. With integers, rounding up is written (n + k − 1) / k: adding k − 1 pushes any leftover over the next whole number. That is how a loop's iteration count is worked out on paper.
Time
O(1)Space
O(1)Java
class Solution {
public int stepLoopCount(int n, int k) {
return (n + k - 1) / k;
}
}