- Combinatorial, Mathematical

Minimum jumps to traverse all integers in range [1, N] such that integer i can jump i steps

Given an integer N, the task is to find the minimum steps to visit all integers in the range [1, N] by selecting any integer and jump i steps at every ith jump.Note: It is possible to revisit an integer more than once. Examples:Input: N = 6Output: 3Explanation: One of the following way is: First start at first number and visit the integers {1, 2, 4}.Now start at 2nd number and visit the integers as {2, 3, 5}Now start at the last number and visit it.Therefor, in total of 3 steps one can visit all the numbers in the range [1, 6]. And also it is the minimum number of steps needed.Input: N = 4Output: 2Naive Approach: The given problem can be solved based on the following observations: In each step the sizes of jumps increases therefore some numbers remains unvisited in a step.Starting from the first number and performing the jumps it can be observed that the maximum size of the jump is the total number of steps needed to visit every number. As in one move, one cannot visit each number between two unvisited numbers.Follow the below steps to solve the problem:Initialize two variables, say count = 1 and res = 0.Traverse over the range [1, N] and increment i by count and update res as res =max(res, count) and increment count by 1.After completing the above steps print the res.Below is the implementation of the above approach:C++#include using namespace std;  int minSteps(int N){        int count = 1, res = 0;          for (int i = 1; i