bhuvesh - 1 year ago 108
Java Question

# increasing code performance of codility

today i heard about this website called codility where a user can give various programming test to check their code's performance.

When I started, they presented me with this sample test,

Task description 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:
`class Solution { public 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

Assume that: X, Y and D are integers within the range

[1..1,000,000,000]; X ≤ Y. Complexity: expected worst-case time

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

The question was pretty straight forward and it took me like 2 minutes to write the solution, which is following,

``````class Solution {
public int solution(int X, int Y, int D) {

int p = 0;
while (X < Y){
p++;
X = X + D;
}
return p;
}
}
``````

However, the test result shows that the performance of my code is just
`20%`
and I scored just
`55%`
,

Here is the link to result, https://codility.com/demo/results/demo66WP2H-K25/

That was so simple code, where I have just used a single
`while`
loop, how could it possibly be make much faster ?

Basic math:

``````X + nD >= Y
nD >= Y - X
n >= (Y - X) / D
``````

The minimum value for n will be the result of rounding up the division of (Y - X) by D.

Big O analysis for this operation:

• Complexity: O(1). It's a difference, a division and a round up
• Worst-case space complexity is O(1): you can have at most 3 more variables:
• Difference for Y - X, let's assign this into Z.
• Division between Z by D, let's assign this into E.
• Rounding E up, let's assign this into R (from result).
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download