Minimum moves to reach target on a infinite line | Set 2
Given a target position on the infinite number line, (-infinity to +infinity). Starting form 0 you have to reach the target by moving as described: In ith move, you can take i steps forward or backward. Find the minimum number of moves required to reach the target.
Examples :
Input : target = 3 Output : 2 Explanation: On the first move we step from 0 to 1. On the second step we step from 1 to 3. Input: target = 2 Output: 3 Explanation: On the first move we step from 0 to 1. On the second move we step from 1 to -1. On the third move we step from -1 to 2.
Approach :
The idea is similar to discussed in O(n) approach here.
Keep adding sum = 1 + 2 + .. + n >= target. Solving this quadratic equation gives the smallest n such that sum >= target, i.e solving for n in n(n+1) / 2 – target >= 0 gives smallest n.
If sum == target, answer is n. Now next case where the sum is greater than the target. Find the difference by how many steps index is ahead of target, i.e sum — target.
Case 1: Difference is even then answered is n, (because there will always a move flipping which will lead to target).
Case 2: Difference is odd, then take one more step, i.e add n+1 to sum and now again take the difference. If the difference is even the n+1 is the answer else take one more move and this will certainly make the difference even then answer will be n + 2.
Explanation: Since the difference is odd. Target is either odd or even.
Case 1 : n is even (1 + 2 + 3 + … + n), then adding n + 1 makes the difference even.
Case 2 : n is odd then adding n + 1 doesn’t makes difference, even so, take one more move, i.e., n+2.
C++
// CPP code to find minimum moves// to reach target#include <bits/stdc++.h>using namespace std;// Function to find minimum steps// to reach targetint StepstoReachTarget(int target){ // Handling negatives // by symmetry target = abs(target); // Keep moving while sum is // smaller i.e calculating n int n = ceil((-1.0 + sqrt(1 + 8.0 * target)) / 2); int sum = n * (n + 1) / 2; if (sum == target) return n; int d = sum - target; // case 1 : d is even if ((d & 1) == 0) return n; // d is odd else return n + ((n & 1) ? 2 : 1);}// Driver codeint main(){ int target = 5; // Function call cout << StepstoReachTarget(target); return 0;} |
Java
// Java code to find minimum moves// to reach targetimport java.lang.*;class GFG { // Function to find minimum steps // to reach target static int StepstoReachTarget(int target) { // Handling negatives // by symmetry target = Math.abs(target); // Keep moving while sum is // smaller i.e calculating n int n = (int)Math.ceil( (-1.0 + (int)Math.sqrt(1 + 8.0 * target)) / 2); int sum = n * (n + 1) / 2; if (sum == target) return n; int d = sum - target; // case 1 : d is even if ((d & 1) == 0) return n; // d is odd else return n + ((n & 1) != 0 ? 2 : 1); } // Driver code public static void main(String[] arg) { int target = 5; // Function call System.out.println(StepstoReachTarget(target)); }}// This code is contributed by// Smitha Dinesh Semwal |
Python3
# Python code to find minimum# moves to reach targetimport math# Function to find minimum# steps to reach targetdef StepstoReachTarget(target): # Handling negatives # by symmetry target = abs(target) # Keep moving while sum is # smaller i.e calculating n n = math.ceil((-1.0 + math.sqrt(1 + 8.0 * target)) / 2) sum = n * (n + 1) / 2 if (sum == target): return n d = sum - target # case 1 : d is even if ((int(d) & 1) == 0): return n # d is odd else: if(int(d) & 1): return n + 2 return n + 1# Driver codetarget = 5# Function callprint(StepstoReachTarget(target))# This code is contributed by# Manish Shaw(manishshaw1) |
C#
// C# code to find minimum moves// to reach targetusing System;class GFG { // Function to find minimum steps // to reach target static int StepstoReachTarget(int target) { // Handling negatives // by symmetry target = Math.Abs(target); // Keep moving while sum is // smaller i.e calculating n int n = (int)Math.Ceiling( (-1.0 + (int)Math.Sqrt(1 + 8.0 * target)) / 2); int sum = n * (n + 1) / 2; if (sum == target) return n; int d = sum - target; // case 1 : d is even if ((d & 1) == 0) return n; // d is odd else return n + ((n & 1) != 0 ? 2 : 1); } // Driver code public static void Main() { int target = 5; // Function call Console.Write(StepstoReachTarget(target)); }}// This code is contributed by nitin mittal. |
PHP
<?php// PHP code to find minimum // moves to reach target// Function to find minimum // steps to reach targetfunction StepstoReachTarget($target){ // Handling negatives$ // by symmetry$ $target = abs($target); // Keep moving while sum is // smaller i.e calculating n $n = ceil((-1.0 + sqrt(1 + 8.0 * $target)) / 2); $sum = $n * ($n + 1) / 2; if ($sum == $target) return $n; $d = $sum - $target; // case 1 : d is even if (($d & 1) == 0) return n; // d is odd else return $n + (($n & 1) ? 2 : 1);}// Driver code$target = 5;// Function callecho StepstoReachTarget($target);// This code is contributed by anuj_67.?> |
Javascript
<script>// JavaScript program to find minimum moves// to reach target// Function to find minimum steps// to reach targetfunction StepstoReachTarget(target){ // Handling negatives // by symmetry target = Math.abs(target); // Keep moving while sum is // smaller i.e calculating n let n = Math.ceil((-1.0 + Math.sqrt(1 + 8.0 * target)) / 2); let sum = n * (n + 1) / 2; if (sum == target) return n; let d = sum - target; // Case 1 : d is even if ((d & 1) == 0) return n; // d is odd else return n + ((n & 1) != 0 ? 2 : 1);}// Driver Codelet target = 5;// Function calldocument.write(StepstoReachTarget(target)); // This code is contributed by avijitmondal1998</script> |
5
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
