The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

Basic Algorithm in this full course refers to algorithms that do not really fall under any particular algorithm heading. This tutorial is the first of such problems.

Problem in Detail

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.

The "catch" for this problem is to be able to produce a O(1) time complexity instead of producing a O(n) time complexity for the number of intervals.

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;
    }

Note that the while condition is (sum < Y), which is the opposite of (sum >= Y), and correct.

The score for this function 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 (or as the value of Y gets bigger and bigger, or both).

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.

The time complexity for the above function is, O(Y-X). This is effectively O(difference), where difference is at least the distance from X to Y, and means n approximately, 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 – 10) divided by 30 would have given 3, with no remainder. That is 100 – 10 = 90 / 30 = 3 R 0. Here D = 30.

However, Y = 85. (85 – 10 ) divided by 30 gives, 2 remainder 15. That is, 85 – 10 = 75 / 30 = 2 R 15 . In order to obtain 3, 1 has to be added to 2 (result of integer division), to give 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 has to be used. That is, either

    (Y - X )  / D = N R 0,  // N taken

OR

    (Y - X )  / D = N R > 0,  //N + 1 taken

And so, for any set of arguments, for parameters 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 <stdio.h> 

    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);
        printf("%i\n", ans);

        return 0; 
    } 

The output is 3, for the given set of arguments, (10, 85, 30). Either the formula, "(Y – X)/D" or "(Y - X)/D + 1" is executed as one operation, for each set of arguments (one pass through the function), and that results in the time complexity, O(1).

The score for the solution() function here, is:

    Task score : 100% -  Correctness : 100% ; Performance : 100%
    Detected time complexity : O(1)

Conclusion

To count the number of jumps in this problem or a similar problem, in constant time, use the formula, which is to subtract the start distance from the end distance, and then divide by the interval (fixed) distance. If the remainder is 0, then the quotient is the answer. If the remainder is not 0, it means that one interval distance still has to be covered; and so 1 has to be added to the whole number part of the quotient, to obtained the answer.