Codility ‘FrogJmp’ Solution

Short Problem Definition:

Count minimal number of jumps from position X to Y.

Link

FrogJmp

Complexity:

expected worst-case time complexity is O(1);

expected worst-case space complexity is O(1).

Execution:

Do not use float division if possible!

Solution:
def solution(X, Y, D):
    if Y < X or D <= 0:
        raise Exception("Invalid arguments")
        
    if (Y- X) % D == 0:
        return (Y- X) // D
    else:
        return ((Y- X) // D) + 1

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • Nehemiah Jacob

    It was a good advice that you mentioned not to use float division thought “return int(ceil(float(Y-X)/D))” scores 100%. Probably Codility hasn’t considered as a tricky case to turn down.

    • BG

      If C++ is used instead of C, your solution should be Okay ( note to include cmath)
      double diff=Y-X;
      long hop = (long)ceil(diff/D);
      return hop;

      https://codility.com/demo/results/training359AYS-KPK/


      • #include
        #include
        #include

        using namespace std;
        using namespace std::chrono;

        int solution(int X, int Y, int D) {
        double diff=Y-X;
        long hop = (long)ceil(diff/D);
        return hop;
        }

        int altSolution(int X, int Y, int D) {
        if ((Y- X) % D == 0)
        return (Y- X) / D;
        else
        return ((Y- X) / D) + 1;
        }

        template
        int timed_template(Lambda &&fnc){
        high_resolution_clock::time_point t1 = high_resolution_clock::now();
        fnc(10, 1000000000, 7);
        high_resolution_clock::time_point t2 = high_resolution_clock::now();
        auto duration = duration_cast( t2 - t1 ).count();
        return duration;
        }

        int main() {
        printf("ceil and double: %d nsn", timed_template(solution));
        printf("modulo fct: %d nsn", timed_template(altSolution));
        return 0;
        }

        With optimisation turned off (-O0):
        ceil and double: 5518 ns
        modulo fct: 62 ns

        With -O3:
        ceil and double: 75 ns
        modulo fct: 32 ns

        • BG

          Thanks a lot for the informative reply from which I learned about chrono.

          However, it seems to me that such a result may not be accurate! I have tried the same code on my PC and had different results each execution. More interesting is that if we replace Ceil-double to be executed after module function, the Ceil-double will show a better performance!!

          for that reason, the code is executed on ideone to have a common environment with you ( please see https://ideone.com/owdyeN)..

          It is an interesting issue for me which should be followed..please share any extra information and correct me if have mistaken something.

  • Son Thai

    well-known trick to integer-divide positive num by positive divisor and round up is (num+(divisor-1))/divisor.
    So in C: return ((Y – X) + (D – 1)) / D; /* the div operator */

  • Арсений Чеботарёв

    Gentlemen, You left me little chances. Well, let’s name it Sorry Mama Solution

    int solution(int X, int Y, int D) {
    __asm__ ("sub %0,%1;idiv %2;cmp $0,%%edx;jz x;inc %%eax;x:"
    ::"b"(X),"a"(Y),"c"(D),"d"(0));
    }

  • Nico
  • Yogendra

    C# Solution :

    class Solution {
    public int solution(int X, int Y, int D) {
    // write your code in C# 6.0 with .NET 4.5 (Mono)

    if(X==Y)
    return 0;

    int _distanceToCover = Y-X;
    int _output = 0;
    if(_distanceToCover <=D)
    {
    return 1;
    }

    if(_distanceToCover % D ==0)
    {
    return _distanceToCover / D;
    }
    else
    {
    return (_distanceToCover / D) + 1;
    }

    return _output;
    }
    }

  • Chima Alaebo

    for JavaScript

    function solution(X, Y, D) {

    // write your code in JavaScript (Node.js 4.0.0)

    var diff = Y-X

    var n = parseInt(diff / D)

    if (diff % D) {

    n++

    }

    return n

    }