FrogJmp at app.codility.com-programmers in C Plus plus Explained - Count minimal number of jumps from position X to Y
Foreword: Category of Article - Technology, Computers and Software, Algorithm
By: Chrysanthus Date Published: 21 Jan 2024
Task
Detected time complexity : O(1)
Lesson 3 at app.codility.com/programmers
The solution and its explanation are given below.
Problem
A small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to a position greater than or equal to Y. The small frog always jumps a fixed distance, D.
Count the minimal number of jumps that the small frog must perform to reach its target.
Write a function:
int solution(int X, int Y, int D);
that, given three integers X, Y and D, returns the minimal number of jumps from position X to a position equal to or greater than Y.
For example, given:
X = 10
Y = 85
D = 30
the function should return 3, because the frog will be positioned as follows:
after the first jump, at position 10 + 30 = 40
after the second jump, at position 10 + 30 + 30 = 70
after the third jump, at position 10 + 30 + 30 + 30 = 100
Write an efficient algorithm for the following assumptions:
X, Y and D are integers within the range [1..1,000,000,000];
X <= Y.
Note:
This problem can be solved in O(n) time complexity or O(1) time complexity. The explanation below begins with O(n) time. After that O(1) time is explained.
O(n) Time
The function for O(n) time is:
int solution(int X, int Y, int D) {
int ctr = 0; //counter
int sum = X;
for (int i=0; sum < Y; i++) {
sum = sum + D;
++ctr;
}
return ctr;
}
The result for this function from app.codility.com/programmers is:
Total Score : 55%
Correctness : 100%
Performance : 20%
This means that the function will always give the correct minimal number of jumps, but gets slower and slower, as the value of D gets smaller and smaller.
The function begins by considering the value of X as the initial total distance covered. The distance covered while the frog is jumping, is held in the variable, sum. The for-loop keeps adding the value of D to sum, while checking if the sum is equal to Y or above, and counting the number of jumps.
Note that the for-loop executes its body first before verifying if the while-condition is true. That is why the while-condition in the parentheses is (sum < Y) and not (sum <= Y). It is also because the counter is initialized to 0.
At app.codility.com/programmers the time complexity for the above function is detected as, O(Y-X). This is effectively O(difference), where difference is at least the distance from X to Y, and means n, giving O(n) time complexity.
O(1) Time
In the question illustration, each time the frog jumps 30 units, a count of 1 is added. The frog finally makes 3 jumps, exceeding 85 units to 100 units, at the last jump. X, Y and D are each an integer.
Now, X = 10. If Y was 100, then (100 \96 10) divided by 30 would have given 3, with no remainder. That is 100 \96 10 = 90 / 30 = 3 R 0. Here D = 30.
However, Y = 85. (85 \96 10 ) divided by 30 gives, 2 remainder 15. That is, 85 \96 10 = 75 / 30 = 2 R 15 . In order to obtain 3, 1 has to be added to 2, to give the 3 .
So, if the difference between Y and X divided by the fixed distance D, has no remainder (R = 0), then the quotient is the number of jumps. If there is a remainder, independent of the value of the remainder, it means that one interval (fixed) distance still has to be covered; and so 1 has to be added to the whole number part of the quotient, to obtain the number of jumps.
So, to obtain the number of jumps, either of two formulas have to be used. That is, either
(Y \96 X ) / D = N R 0, // N taken
OR
(Y \96 X ) / D = N R > 0, //N + 1 taken
And so, for any set of arguments, for X, Y and D, one of the two formulas (not both) has to be executed. That is constant time, which is same as O(1) time.
The constant time function (program) is:
#include <iostream>
using namespace std;
int solution(int X, int Y, int D) {
if ((Y - X)%D == 0)
return (Y - X)/D;
else
return (Y - X)/D + 1;
}
int main()
{
int ans = solution(10, 85, 30);
cout << ans << endl;
return 0;
}
The output is 3, for the given set of arguments, (10, 85, 30). Either the formula, \93(Y \96 X)/D\94 or \93(Y - X)/D + 1\94 is executed as one operation, for each set of arguments (one pass through the function), and that results in the time complexity, O(1).
Remember that at app.codility.com, the C++ main function is not typed (not submitted). This C++ main() function has only one test case, which is given in the illustration of the problem above.
The reader should register at app.codility.com and be testing his/her code, to gain confidence. The score for the solution() function here, is:
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(1)
Lesson 3 at app.codility.com/programmers
Conclusion
The reader should register at app.codility.com/programmers, so that he/she should be testing his/her code.