Given an array, arr[] of N positive integers and an integer K. It is given that you start at position 0 and you can move to left or right by a[i] positions starting from arr[0]. The task is to print the direction of moves so that you can complete N steps without exceeding the [-K, +K] boundary by moving right or left. In case you cannot perform steps, print -1. In case of multiple answers, print anyone.
Examples:
Input: arr[] = {40, 50, 60, 40}, K = 120
Output:
Right
Right
Left
Right
Explanation :
Since N = 4 (Number of elements in the array),
we need to make 4 moves from arr[0] such that
value does not go out of [-120, 120]
Move 1: Position = 0 + 40 = 40
Move 2: Position = 40 + 50 = 90
Move 3: Position = 90 – 60 = 30
Move 4: Position = 30 + 50 = 80
Input: arr[] = {40, 50, 60, 40}, K = 20
Output: -1
Approach: The following steps can be followed to solve the above problem:
- Initialize position to 0 in the beginning.
- Start traversing all the array elements,
- If a[i] + position does not exceed the left and the right boundary, then the move will be “Right”.
- If position – a[i] does not exceed the left and the right boundary, then the move will be “Left”.
- If at any stage both the condition fail then print -1.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to print steps such that// they do not cross the boundaryvoid printSteps(int a[], int n, int k){ // To store the resultant string string res = ""; // Initially at zero-th position int position = 0; int steps = 1; // Iterate for every i-th move for (int i = 0; i < n; i++) { // Check for right move condition if (position + a[i] <= k && position + a[i] >= (-k)) { position += a[i]; res += "Right\n"; } // Check for left move condition else if (position - a[i] >= -k && position - a[i] <= k) { position -= a[i]; res += "Left\n"; } // No move is possible else { cout << -1; return; } } // Print the steps cout << res;}// Driver codeint main(){ int a[] = { 40, 50, 60, 40 }; int n = sizeof(a) / sizeof(a[0]); int k = 120; printSteps(a, n, k); return 0;} |
Java
// Java implementation of the approachclass GFG{ // Function to print steps such that// they do not cross the boundarystatic void printSteps(int []a, int n, int k){ // To store the resultant string String res = ""; // Initially at zero-th position int position = 0; //int steps = 1; // Iterate for every i-th move for (int i = 0; i < n; i++) { // Check for right move condition if (position + a[i] <= k && position + a[i] >= (-k)) { position += a[i]; res += "Right\n"; } // Check for left move condition else if (position - a[i] >= -k && position - a[i] <= k) { position -= a[i]; res += "Left\n"; } // No move is possible else { System.out.println(-1); return; } } // Print the steps System.out.println(res);}// Driver codepublic static void main (String[] args){ int []a = { 40, 50, 60, 40 }; int n = a.length; int k = 120; printSteps(a, n, k);}}// This code is contributed by mits |
Python3
# Python3 implementation of the approach# Function to print steps such that# they do not cross the boundarydef printSteps(a, n, k): # To store the resultant string res = "" # Initially at zero-th position position = 0 steps = 1 # Iterate for every i-th move for i in range(n): # Check for right move condition if (position + a[i] <= k and position + a[i] >= -k): position += a[i] res += "Right\n" # Check for left move condition elif (position-a[i] >= -k and position-a[i] <= k): position -= a[i] res += "Left\n" # No move is possible else: print(-1) return print(res)# Driver codea = [40, 50, 60, 40]n = len(a)k = 120printSteps(a, n, k)# This code is contributed by Shrikant13 |
C#
// C# implementation of the approachusing System;class GFG{ // Function to print steps such that// they do not cross the boundarystatic void printSteps(int []a, int n, int k){ // To store the resultant string String res = ""; // Initially at zero-th position int position = 0; //int steps = 1; // Iterate for every i-th move for (int i = 0; i < n; i++) { // Check for right move condition if (position + a[i] <= k && position + a[i] >= (-k)) { position += a[i]; res += "Right\n"; } // Check for left move condition else if (position - a[i] >= -k && position - a[i] <= k) { position -= a[i]; res += "Left\n"; } // No move is possible else { Console.WriteLine(-1); return; } } // Print the steps Console.Write(res);}// Driver codestatic void Main(){ int []a = { 40, 50, 60, 40 }; int n = a.Length; int k = 120; printSteps(a, n, k);}}// This code is contributed by mits |
PHP
<?php// PHP implementation of the approach// Function to print steps such that// they do not cross the boundaryfunction printSteps($a, $n, $k){ // To store the resultant string $res = ""; // Initially at zero-th position $position = 0; $steps = 1; // Iterate for every i-th move for ($i = 0; $i < $n; $i++) { // Check for right move condition if ($position + $a[$i] <= $k && $position + $a[$i] >= (-$k)) { $position += $a[$i]; $res .= "Right\n"; } // Check for left move condition else if ($position - $a[$i] >= -$k && $position - $a[$i] <= $k) { $position -= $a[$i]; $res .= "Left\n"; } // No move is possible else { echo -1; return; } } // Print the steps echo $res;}// Driver code$a = array( 40, 50, 60, 40 );$n = count($a);$k = 120;printSteps($a, $n, $k);// This code is contributed by mits?> |
Javascript
<script>// javascript implementation of the approach // Function to print steps such that // they do not cross the boundary function printSteps(a , n , k) { // To store the resultant string var res = ""; // Initially at zero-th position var position = 0; // var steps = 1; // Iterate for every i-th move for (i = 0; i < n; i++) { // Check for right move condition if (position + a[i] <= k && position + a[i] >= (-k)) { position += a[i]; res += "Right<br/>"; } // Check for left move condition else if (position - a[i] >= -k && position - a[i] <= k) { position -= a[i]; res += "Left<br/>"; } // No move is possible else { document.write(-1); return; } } // Print the steps document.write(res); } // Driver code var a = [ 40, 50, 60, 40 ]; var n = a.length; var k = 120; printSteps(a, n, k);// This code is contributed by todaysgaurav</script> |
Output:
Right Right Left Right
Time Complexity: O(N), as we are using a loop to traverse N times. Where N is the number of elements in the array.
Auxiliary Space: O(N), as we are using extra space for the string res. Where N is the number of elements in the array.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!