Codility ‘FrogJmp’ Solution

Short Problem Definition:

Count minimal number of jumps from position X to Y.

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.

• 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

}

• Alper Aykac

%100 performance and correctness in java

public int solution(int X, int Y, int D) {
int kalan = (Y – X) % D;
int adim = kalan == 0 ? (Y – X) / D :(Y – X – kalan) / D + 1 ;
``` function solution(X, Y, D) { return Math.ceil((Y-X)/D); } ```