CountDiv at Codility-programmers in C Plus Plus Explained - Compute number of integers divisible by k in range [a..b]
Foreword: Category of Article - Technology, Computers and Software, Algorithm
By: Chrysanthus Date Published: 29 Jan 2024
Task
Detected time complexity : Constant Time, O(1)
Lesson 5 at app.codility.com/programmers
The solution and its explanation are given below.
Problem
Title of Problem: CountDiv, for "Counting Division Intervals"
Write a function:
int solution(int A, int B, int K);
that, given three integers A, B and K, returns the number of integers within the range [A..B] that are divisible by K, i.e.
{ i : A <= i <= B, i mod K = 0 }
For example, for A = 6, B = 11 and K = 2, your function should return 3, because there are three numbers divisible by 2 within the range [6..11], namely 6, 8 and 10.
Write an efficient algorithm for the following assumptions:
- A and B are integers within the range [0..2,000,000,000];
- K is an integer within the range [1..2,000,000,000];
- A <= B.
Note:
The left limit is A and the right limit is B, indicated by [A..B]. Both limit integers are included as possible required dividends. 'A' may or may not be divisible by K. B may or may not be divisible by K. The integers in between, may or may not be divisible by K.
Brute Force Approach
The brute force approach test all the integers from 'A' to B (inclusive). This takes O(n) time complexity (from A to B, inclusive). In this situation, O(n) is almost O(B - A). Precisely, O(n) = O(B - A +1). To know if an integer is divisible by K, use the modulus operator, %. If the remainder is 0, then it is divisible by K. The brute force approach program is:
#include <iostream>
using namespace std;
int solution(int A, int B, int K) {
int num = 0;
for (int i=A; i<=B; i++) {
if (i%K == 0)
num += 1; // same as num = num + 1
}
return num;
}
int main()
{
int ret = solution(6, 11, 2);
cout << ret << endl;
return 0;
}
At app.codility.com/programmers, the scoring and detected time complexity for this brute force approach is:
Task score : 50% - Correctness : 100% ; Performance : 0%
Detected time complexity: O(B-A), same as O(n), where n is B - A, though n is actually B-A+1.
This approach takes O(n) time complexity (from A to B, inclusive).
Smart Approach
There are two situations here: the situation where A is divisible by K and the situation where A is not divisible by K.When A is Divisible by K
K is less than Or Equal to (B - A)
Summing K as an interval, from A to B is the same as summing K as an interval from 0 to (B - A), beginning from the first divisible integer.
Under this condition, the number of integers divisible by K in the range [A..B], is the same as the number of integers divisible by K in the range 0 to (B - A), including 0. That is, the range (B - A) has been translated down to begin at zero. Since A is divisible by K under this condition, it means that 0 has to be considered as divisible by K.
Using the above sample case, (11 - 6) = 5 and K = 2. From 0 to 5, intervals of 2 occurs 2 times, from 2 to 4. That is, 0 + 2 = 2 and 2 + 2 = 4. From 6 to 11, 6 is divisible by 2. Adding 2 to 6 is 8; and 8 is divisible by 2. Adding 2 to 8 is 10; and 10 is divisible by 2. This makes a count of 3, for number of integers divisible by 2, from 6 to 11, inclusive. However, there are only two intervals of 2, in both corresponding ranges. Since 6 in the range, [6..11] is divisible by 2, then 0 in the range [0..5] has to be considered as divisible by 2, to make the count 3, from 0 to 5, instead of 2, in the range, 0 to (B - A), inclusive.
So, the number of required dividends, is obtained from the integer division,
(B - A)/k +1
where (B - A)/k is the number of intervals, and +1 accounts for the A divisible by K (corresponding to 0 divisible by K). With the sample case given,
(11 - 6)/2 + 1 = 5/2 + 1 = 2 and a half + 1 = 2 + 1 = 3
Integer division truncates (off) any fraction, even if the fraction is greater than 1/2 (making 2 and a half, as 2). Again, the addition of 1, accounts for A (or 0), if A from [A..B] is divisible by K.
There is trouble! The problem is, in C++, "(B - A)/k +1" as integer division, does not give the right answer all the times, for different test cases, because of the way integer division is done in C++. Since the floating number division of (B - A)/k is the same as B/K + A/K, mathematically, then the solution in C++, is to use the following integer divisions plus 1:
B/K - A/K + 1
where B/K and A/K are C++ integer divisions with truncation.
In this case, it is not possible to have more than zero interval of K from A to B (inclusive). In this situation, it is only possible to have at most one divisible dividend from A to B (inclusive), which is just A.
Consider the case, where A = 10, B = 14 and K = 5: B - A = 14 - 10 = 4, and K = 5 is greater than 4. The only possible dividend here, is 10 = A, as 10 / 5 = 2 remainder 0. Substituting into the above formula gives,
B/K - A/K + 1 = 14/5 - 10/5 + 1 = [2 + 4/5] - [2 + 0] + 1
With integer division, the fraction, 4/5 is ignored, leading to, 2 - 2 + 1 = 0 + 1 = 1 , and correct.
When A is not Divisible by K
K is less than Or Equal to (B - A)
Consider another sample case, where K=10, A = 16 and B = 53. A (16) is not divisible by 10. 20 is divisible by 10. 20 is the first required dividend, in the range 16 to 53 (inclusive). 20 + 10 = 30 is divisible by 10. 30 is the second required dividend. 30 + 10 = 40 is divisible by 10. 40 is the third required dividend. 40 + 10 = 50 is divisible by 10. 50 is the fourth required dividend. 50 + 10 = 60, which crosses the range. B (53) is not divisible by 10. The number of integers in the range, [16..53] that are divisible by 10 is 4.
The integer division,
(B - A)/k
where (B - A)/k is the number of intervals (without +1), in the range, A to B (inclusive), should be considered here. With the current sample case,
(53 - 16)/10 = 37/10 = [3 +7/10] = 3,
since integer division in C++ will truncate off the fraction, 7/10. Three appears here as the number of intervals from the first required dividend. The actual number of required dividends in the range, 16 to 53 (inclusive), is 4, as determined above. Something is wrong! What about the C++ integer division of 53/10 - 16/10 ? That gives:
53/10 - 16/10 = [5 + 3/10] - [1 + 6/10] = 5 - 1 = 4, the correct answer
as integer division in C++ will truncate off the fractions, 3/10 and 6/10. The reader should accept that, when A is not divisible by K, and K is less than or equal to (B - A), the C++ integer division formula of
B/K - A/K
gives the correct answer (number of dividends). Since A or its corresponding 0 is not divisible by K here, 1 is not added to the expression.
Situation where K is greater than (B - A), and less than or equal to B, but A is not divisible by K
In this case, it is not possible to have more than zero interval of K from A to B (inclusive). In this situation, it is only possible to have at most one divisible dividend from A to B (inclusive).
Consider another sample case, where K=10, A = 46 and B = 53. B - A = 53 - 46 = 7. There is only one number from 46 to 53 (inclusive), that is divisible by 10, and that number is 50. Using the formula, B/K - A/K, gives
53/10 - 46/10 = [5 + 3/10] - [4 + 6/10] = 5 - 4 = 1, and correct.
The fraction, 3/10 and 4/10 are truncated off by C++ integer division. The reader should accept that, when A is not divisible by K and K is greater than (B - A), but less than or equal to B, the C++ integer division formula of
B/K - A/K
gives the correct answer (number of dividends). With K = 20 and A = 46 with B = 53, no integer in the range, [A..B] = [46..53] is divisible by 20 and the formula gives the correct answer with,
53/20 - 46/20 = [2 + 13/20] - [2 + 6/20] = 2 - 2 = 0
Situation of K being greater than B
If K is greater than B, then no integer in the range, A to B (inclusive), would be divisible by K. This is not a condition to take into consideration.
The two Situations Combined using Pseudo-Code:
if (A is divisible by K)
answer = B/K - A/K + 1 //C++ integer division
else
answer = B/K - A/K //C++ integer division
If the else-part is not coded, then it has to be replaced by a return statement. The smart program is:
#include <iostream>
using namespace std;
int solution(int A, int B, int K) {
if (A%K == 0)
return B/K - A/K + 1;
return B/K - A/K;
}
int main()
{
int ret = solution(6, 11, 2);
cout << ret << endl;
return 0;
}
The output is 3. In the if-compound statement, only either the if-part is executed or the else part is executed. So only one operation takes place for the solution() function. At app.codility.com/programmers, the scoring and detected time complexity for this smart approach is:
Detected time complexity: constant time, O(1)
Task score : 100% - Correctness : 100% ; Performance : 100%
Conclusion
The pseudo code is:
if (A is divisible by K)
answer = B/K - A/K + 1 //C++ integer division
else
answer = B/K - A/K //C++ integer division
The reader should register at app.codility.com/programmers, so that he/she should be testing his/her code.