Make an array strictly increasing by repeatedly subtracting and adding arr[i – 1] – (i – 1) to adjacent indices
Given an array arr[] consisting of N positive integers, the task is to check whether the given array arr[] can be made strictly increasing such that for any index i from the range [1, N – 1], if (arr[i – 1] – (i – 1)) is at least 0, then it is added to arr[i] and subtracted from arr[i – 1]. If it is possible to make the array strictly increasing, then print Yes. Otherwise, print No.
Examples:
Input: arr[] = {1, 5, 2, 7, 6}
Output: Yes
Explanation:
Consider the following operations:
- Choosing the index 1, the value of arr[i – 1] – (i – 1) is 1, which is at least 0. Adding 1 to arr[1] and subtracting it from arr[0], modifies the array to {0, 6, 2, 7, 6}.
- Choosing the index 2, the value of arr[i – 1] – (i – 1) is 5, which is at least 0. Adding 5 to arr[2] and subtracting it from arr[1], modifies the array to {0, 1, 7, 7, 6}.
- Choosing the index 3, the value of arr[i – 1] – (i – 1) is 5, which is at least 0. Adding 6 to arr[3] and subtracting it from arr[2], modifies the array to {0, 1, 2, 12, 6}.
- Choosing the index 4, the value of arr[i – 1] – (i – 1) is 9, which is at least 0. Adding 9 to arr[4] and subtracted from arr[3], modifies the array to {0, 1, 2, 3, 15}.
After the above operations, the array becomes strictly increasing.
Input: arr[] = {0, 1, 0}
Output: No
Approach: The given problem can be solved by using the Greedy Approach. Follow the steps below to solve the problem
- Traverse the given array using variable i in range [1, N – 1] and perform the following steps:
- If arr[i – 1] is at least (i – 1), then perform the following steps:
- Store the value of arr[i] – arr[i – 1] in a variable, say P.
- Update arr[i – 1] as arr[i – 1] – P.
- Update arr[i] as arr[i] + P.
- If arr[i – 1] is at least (i – 1), then perform the following steps:
- After completing the above steps, if the array arr[] is sorted, then print “Yes”. Otherwise, print “No”
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if an array // can be made strictly increasing void check( int arr[], int n) { // Traverse the given array arr[] for ( int i = 1; i < n; i++) { if (arr[i - 1] >= (i - 1)) { // Update the value of p, // arr[i], and arr[i - 1] int p = arr[i - 1] - (i - 1); arr[i] += p; arr[i - 1] -= p; } } // Traverse the given array for ( int i = 1; i < n; i++) { // Check if the array arr[] is // strictly increasing or not if (arr[i] <= arr[i - 1]) { cout << "No" ; return ; } } // Otherwise, array is increasing // order, print Yes cout << "Yes" ; } // Driver Code int main() { int arr[] = { 1, 5, 2, 7, 6 }; int N = sizeof (arr) / sizeof (arr[0]); check(arr, N); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG{ // Function to check if an array // can be made strictly increasing static void check( int arr[], int n) { // Traverse the given array arr[] for ( int i = 1 ; i < n; i++) { if (arr[i - 1 ] >= (i - 1 )) { // Update the value of p, // arr[i], and arr[i - 1] int p = arr[i - 1 ] - (i - 1 ); arr[i] += p; arr[i - 1 ] -= p; } } // Traverse the given array for ( int i = 1 ; i < n; i++) { // Check if the array arr[] is // strictly increasing or not if (arr[i] <= arr[i - 1 ]) { System.out.println( "No" ); return ; } } // Otherwise, array is increasing // order, print Yes System.out.println( "Yes" ); } // Driver Code public static void main(String[] args) { int arr[] = { 1 , 5 , 2 , 7 , 6 }; int N = arr.length; check(arr, N); } } // This code is contributed by Dharanendra L V. |
Python3
# Python3 program for the above approach # Function to check if an array # can be made strictly increasing def check(arr, n): # Traverse the given array arr[] for i in range ( 1 , n): if (arr[i - 1 ] > = (i - 1 )): # Update the value of p, # arr[i], and arr[i - 1] p = arr[i - 1 ] - (i - 1 ) arr[i] + = p arr[i - 1 ] - = p # Traverse the given array for i in range ( 1 , n): # Check if the array arr[] is # strictly increasing or not if (arr[i] < = arr[i - 1 ]): print ( "No" ) return # Otherwise, array is increasing # order, print Yes print ( "Yes" ) # Driver Code if __name__ = = '__main__' : arr = [ 1 , 5 , 2 , 7 , 6 ] N = len (arr) check(arr, N) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to check if an array // can be made strictly increasing static void check( int []arr, int n) { // Traverse the given array arr[] for ( int i = 1; i < n; i++) { if (arr[i - 1] >= (i - 1)) { // Update the value of p, // arr[i], and arr[i - 1] int p = arr[i - 1] - (i - 1); arr[i] += p; arr[i - 1] -= p; } } // Traverse the given array for ( int i = 1; i < n; i++) { // Check if the array arr[] is // strictly increasing or not if (arr[i] <= arr[i - 1]) { Console.Write( "No" ); return ; } } // Otherwise, array is increasing // order, print Yes Console.Write( "Yes" ); } // Driver Code public static void Main() { int []arr = { 1, 5, 2, 7, 6 }; int N = arr.Length; check(arr, N); } } // This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script> // Javascript program for the above approach // Function to check if an array // can be made strictly increasing function check(arr, n) { // Traverse the given array arr for ( var i = 1; i < n; i++) { if (arr[i - 1] >= (i - 1)) { // Update the value of p, // arr[i], and arr[i - 1] var p = arr[i - 1] - (i - 1); arr[i] += p; arr[i - 1] -= p; } } // Traverse the given array for ( var i = 1; i < n; i++) { // Check if the array arr is // strictly increasing or not if (arr[i] <= arr[i - 1]) { document.write( "No" ); return ; } } // Otherwise, array is increasing // order, print Yes document.write( "Yes" ); } // Driver Code var arr = [ 1, 5, 2, 7, 6 ]; var N = arr.length; check(arr, N); // This code is contributed by 29AjayKumar </script> |
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)