Close

Minimum number of jumps to reach top

There are N steps in a staircase, and a person can jump 5 steps at max, i.e he can jump any number of steps between 1 and 5.
What is the minumum number of jumps he has to make to reach the top?
A simple math problem which can be solved using a simple greedy approach. Try to make as many maximum jumps as possible before reaching the top. Take a smaller jump if needed at the end.
For example if there are 10 steps, he can make two maximum jumps of 5 steps each to reach the top.
If there 8 steps, First he can jump 5 steps and then jump 3 steps. So within 2 jumps, he can reach the top.
The code for this very simple. This problem can also be generalized by customizing the jump capacity to any number instead of a fixed number 5.

#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
  int loc;
  scanf("%d", &loc);
  printf("%d\n",loc/5 + (loc%5 == 0?0:1));
  return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *