Find a number in minimum steps | Java program to Find a number in minimum steps ; Steps sequence ; Current sum ; Sign of the number ; Basic steps required to get sum >= required value . ; If we have reached ahead to destination . ; If the last step was an odd number , then it has following mechanism for negating a particular number and decreasing the sum to required number Also note that it may require 1 more step in order to reach the sum . ; If the current time instance is even and sum is odd than it takes 2 more steps and few negations in previous elements to reach there . ; Driver Program
import java . util . * ; class GFG { static Vector < Integer > find ( int n ) { Vector < Integer > ans = new Vector < > ( ) ; int sum = 0 ; int i = 1 ; int sign = ( n >= 0 ? 1 : - 1 ) ; n = Math . abs ( n ) ; for ( ; sum < n ; ) { ans . add ( sign * i ) ; sum += i ; i ++ ; } if ( sum > sign * n ) { if ( i % 2 != 0 ) { sum -= n ; if ( sum % 2 != 0 ) { ans . add ( sign * i ) ; sum += i ; i ++ ; } int a = ans . get ( ( sum / 2 ) - 1 ) ; ans . remove ( ( sum / 2 ) - 1 ) ; ans . add ( ( ( sum / 2 ) - 1 ) , a * ( - 1 ) ) ; } else { sum -= n ; if ( sum % 2 != 0 ) { sum -- ; ans . add ( sign * i ) ; ans . add ( sign * - 1 * ( i + 1 ) ) ; } ans . add ( ( sum / 2 ) - 1 , ans . get ( ( sum / 2 ) - 1 ) * - 1 ) ; } } return ans ; } public static void main ( String [ ] args ) { int n = 20 ; if ( n == 0 ) System . out . print ( "Minimum number of Steps: 0 Step sequence : 0 "); else { Vector < Integer > a = find ( n ) ; System . out . print ( " Minimum ▁ number ▁ of ▁ Steps : ▁ " + a . size ( ) + " Step sequence : "); for ( int i : a ) System . out . print ( i + " ▁ " ) ; } } }