Minimal number of jumps

  • May 11, 2022

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.

Let’s write an efficient algorithm for the following assumptions:

  • X, Y and D are integers within the range [1..1,000,000,000];
  • X ≤ Y.

{example1}

1
2
3
4
5
6
7
8

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

Solution:

{codeString1}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class FrogJump {
        companion object {
            @JvmStatic
            fun main(args: Array<String>) {
                println("(10,85,30) \${solution(10, 85, 30)}")
                println("(10,85,20) \${solution(10, 85, 20)}")
                println("(10,81,20) \${solution(10, 81, 20)}")
                println("(10,90,20) \${solution(10, 90, 20)}")
                println("(10,91,20) \${solution(10, 91, 20)}")
            }
    
            fun solution(X: Int, Y: Int, D: Int): Int {
                val distance = Y - X
                return Math.ceil(distance.toDouble()/D).toInt()
            }
        }
    
    }

Tags :
comments powered by Disqus

Related Posts

Binary Gap

A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.

Read More

Rotate Array

An array A consisting of N integers is given. Rotation of the array means that each element is shifted right by one index, and the last element of the array is moved to the first place.

Read More