Minimum steps required to reduce all array elements to 1 based on given steps
Given an array arr[] of size N. The task is to find the minimum steps required to reduce all array elements to 1. In each step, perform the following given operation:
- Choose any starting index, say i, and jump to the (arr[i] + i)th index, reducing ith as well as (arr[i] + i)th index by 1, follow this process until it reaches the end of the array
- If an element is already reduced to 1, it can’t be reduced more, it remains the same.
Examples:
Input: arr[] = {4, 2, 3, 2, 2, 2, 1, 2}, N = 8
Output: 5
Explanation: Series of operations can be performed in the following way:
- {4, 2, 3, 2, 2, 2, 1, 2}, decrement values by 1, arr[] = {4, 2, 2, 2, 2, 1, 1, 1}
- {4, 2, 2, 2, 2, 1, 1, 1}, decrement values by 1, arr[] = {3, 2, 2, 2, 1, 1, 1, 1}
- {3, 2, 2, 2, 1, 1, 1, 1}, decrement values by 1, arr[] = {2, 2, 2, 1, 1, 1, 1, 1}
- {2, 2, 2, 1, 1, 1, 1, 1}, decrement values by 1, arr[] = {1, 2, 1, 1, 1, 1, 1, 1}
- {1, 2, 1, 1, 1, 1, 1, 1}, decrement values by 1, arr[] = {1, 1, 1, 1, 1, 1, 1, 1}
So, total steps required = 5
Input: arr[] = {1, 3, 1, 2, 2}, N = 5
Output: 2
Approach: The given problem can be solved by dividing the problem in 4 parts :- (0 to i-1) | i | (i + 1) | (i + 2 to n – 1). Follow the below steps to solve the problem:
- Take a vector say v, which will denote how many times an element is decreased due to visiting the previous elements.
- Each element in v i.e v[i] denotes the count of decrement in arr[i] due to visiting the elements from 0 to (i-1).
- Iterate over the array arr[], and take a variable say k to store the numbers of passes that have to add in answer due to element arr[i] after making 0 to (i-1) elements equal to 1.
- Inside the loop, run another loop(i.e the second loop) to compute how much current arr[i] elements effect(decrease after visiting the ith element) the (i+2) to N elements.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find minimum steps // required to reduce all array // elements to 1 int minSteps( int arr[], int N) { // Variable to store the answer int steps = 0; // Vector with all elements initialized // with 0 vector< long long > v(N + 1, 0); // Traverse the array for ( int i = 0; i < N; ++i) { // Variable to store the numbers of // passes that have to add in answer // due to element arr[i] after making // 0 to (i-1) elements equal to 1 int k = max(0ll, arr[i] - 1 - v[i]); // Increment steps by K steps += k; // Update element in v v[i] += k; // Loop to compute how much current element // effect the (i+2) to N elements for ( int j = i + 2; j <= min(i + arr[i], N); j++) { v[j]++; } v[i + 1] += v[i] - arr[i] + 1; } // Return steps which is the answer return steps; } // Driver Code int main() { int arr[] = { 4, 2, 3, 2, 2, 2, 1, 2 }; int N = sizeof (arr) / sizeof (arr[0]); cout << minSteps(arr, N); return 0; } |
Java
// Java code for the above approach import java.io.*; class GFG { // Function to find minimum steps // required to reduce all array // elements to 1 static int minSteps( int arr[], int N) { // Variable to store the answer int steps = 0 ; // Vector with all elements initialized // with 0 int v[] = new int [N + 1 ]; // Traverse the array for ( int i = 0 ; i < N; ++i) { // Variable to store the numbers of // passes that have to add in answer // due to element arr[i] after making // 0 to (i-1) elements equal to 1 int k = Math.max( 0 , arr[i] - 1 - v[i]); // Increment steps by K steps += k; // Update element in v v[i] += k; // Loop to compute how much current element // effect the (i+2) to N elements for ( int j = i + 2 ; j <= Math.min(i + arr[i], N); j++) { v[j]++; } v[i + 1 ] += v[i] - arr[i] + 1 ; } // Return steps which is the answer return steps; } // Driver Code public static void main(String[] args) { int arr[] = { 4 , 2 , 3 , 2 , 2 , 2 , 1 , 2 }; int N = arr.length; System.out.println(minSteps(arr, N)); } } // This code is contributed by Potta Lokesh |
Python3
# Python program for the above approach # Function to find minimum steps # required to reduce all array # elements to 1 def minSteps(arr, N): # Variable to store the answer steps = 0 # Vector with all elements initialized # with 0 v = [ 0 ] * (N + 1 ) # Traverse the array for i in range (N): # Variable to store the numbers of # passes that have to add in answer # due to element arr[i] after making # 0 to (i-1) elements equal to 1 k = max ( 0 , arr[i] - 1 - v[i]) # Increment steps by K steps + = k # Update element in v v[i] + = k # Loop to compute how much current element # effect the (i+2) to N elements for j in range (i + 2 , min (i + arr[i], N) + 1 ): v[j] + = 1 v[i + 1 ] + = v[i] - arr[i] + 1 # Return steps which is the answer return steps # Driver Code arr = [ 4 , 2 , 3 , 2 , 2 , 2 , 1 , 2 ] N = len (arr) print (minSteps(arr, N)) # This code is contributed by gfgking. |
C#
// C# code for the above approach using System; class GFG { // Function to find minimum steps // required to reduce all array // elements to 1 static int minSteps( int [] arr, int N) { // Variable to store the answer int steps = 0; // Vector with all elements initialized // with 0 int [] v = new int [N + 1]; // Traverse the array for ( int i = 0; i < N; ++i) { // Variable to store the numbers of // passes that have to add in answer // due to element arr[i] after making // 0 to (i-1) elements equal to 1 int k = Math.Max(0, arr[i] - 1 - v[i]); // Increment steps by K steps += k; // Update element in v v[i] += k; // Loop to compute how much current element // effect the (i+2) to N elements for ( int j = i + 2; j <= Math.Min(i + arr[i], N); j++) { v[j]++; } v[i + 1] += v[i] - arr[i] + 1; } // Return steps which is the answer return steps; } // Driver Code public static void Main() { int [] arr = { 4, 2, 3, 2, 2, 2, 1, 2 }; int N = arr.Length; Console.Write(minSteps(arr, N)); } } // This code is contributed by gfgking |
Javascript
<script> // JavaScript program for the above approach // Function to find minimum steps // required to reduce all array // elements to 1 const minSteps = (arr, N) => { // Variable to store the answer let steps = 0; // Vector with all elements initialized // with 0 let v = new Array(N + 1).fill(0); // Traverse the array for (let i = 0; i < N; ++i) { // Variable to store the numbers of // passes that have to add in answer // due to element arr[i] after making // 0 to (i-1) elements equal to 1 let k = Math.max(0, arr[i] - 1 - v[i]); // Increment steps by K steps += k; // Update element in v v[i] += k; // Loop to compute how much current element // effect the (i+2) to N elements for (let j = i + 2; j <= Math.min(i + arr[i], N); j++) { v[j]++; } v[i + 1] += v[i] - arr[i] + 1; } // Return steps which is the answer return steps; } // Driver Code let arr = [4, 2, 3, 2, 2, 2, 1, 2]; let N = arr.length document.write(minSteps(arr, N)); // This code is contributed by rakeshsahni </script> |
Output:
5
Time Complexity: O(N2)
Auxiliary Space: O(N)