Count Multiples of K up to N
Solve this ProblemEasy5 min
Topics
BasicsComplexityMath
Companies
TCSInfosysWipro
Given
n and k, return how many of the numbers 1, 2, …, n are multiples of k.
This is a small example of why performancePerformanceHow much time (and memory) a program needs, especially as its input gets larger. matters. A check-every-number loop is fine for n = 20 but does a million checks for n = 10⁶ — and real programs run such code thousands of times. A little thinking turns the whole loop into a single division. Both are correct; only one scalesScalabilityHow well a solution keeps up as the input grows much larger..
Test Case 1:
Input:n = 20, k = 6
Output:3
Explanation:6, 12 and 18 are the multiples of 6 that do not exceed 20.
Test Case 2:
Input:n = 5, k = 9
Output:0
Explanation:The first multiple, 9, is already larger than 5.
Constraints
- ◆
1 ≤ n ≤ 1000000 - ◆
1 ≤ k ≤ 1000000
Try the Dry Run
Approach & Solutions
Check Every NumberBrute
Look at each number from 1 to n and count the ones that k divides exactly. It is obviously correct, but it touches all n numbers even when only a few of them matter — a million checks for n = 10⁶.
Time
O(n)Space
O(1)Java
class Solution {
public int countMultiples(int n, int k) {
int count = 0;
for (int i = 1; i <= n; i++) {
if (i % k == 0) {
count++;
}
}
return count;
}
}Divide OnceOptimal
The multiples of k up to n are k, 2k, 3k, …, and the last one is the largest m·k ≤ n. So the count is simply how many whole times k fits into n: n / k with integer division. One operation instead of n.
Time
O(1)Space
O(1)Java
class Solution {
public int countMultiples(int n, int k) {
return n / k;
}
}