Check whether an array can be made strictly increasing by modifying atmost one element
Given an array arr[] of positive integers, the task is to find whether it is possible to make this array strictly increasing by modifying atmost one element.
Examples:
Input: arr[] = {2, 4, 8, 6, 9, 12}
Output: Yes
By modifying 8 to 5, array will become strictly increasing.
i.e. {2, 4, 5, 6, 9, 12}
Input: arr[] = {10, 5, 2}
Output: No
Approach: For every element arr[i], if it is greater than both arr[i – 1] and arr[i + 1] or it is smaller than both arr[i – 1] and arr[i + 1] then arr[i] needs to be modified.
i.e. arr[i] = (arr[i – 1] + arr[i + 1]) / 2. If after modification, arr[i] = arr[i – 1] or arr[i] = arr[i + 1] then the array cannot be made strictly increasing without affecting more than a single element. Else count all such modifications, if the count of modifications in the end is less than or equal to 1 then print “Yes” else print “No”.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <iostream> using namespace std; // Function that returns true if arr[] // can be made strictly increasing after // modifying at most one element bool check( int arr[], int n) { // To store the number of modifications // required to make the array // strictly increasing int modify = 0; // Check whether the first element needs // to be modify or not if (arr[0] > arr[1]) { arr[0] = arr[1] / 2; modify++; } // Loop from 2nd element to the 2nd last element for ( int i = 1; i < n - 1; i++) { // Check whether arr[i] needs to be modified if ((arr[i - 1] < arr[i] && arr[i + 1] < arr[i]) || (arr[i - 1] > arr[i] && arr[i + 1] > arr[i])) { // Modifying arr[i] arr[i] = (arr[i - 1] + arr[i + 1]) / 2; // Check if arr[i] is equal to any of // arr[i-1] or arr[i+1] if (arr[i] == arr[i - 1] || arr[i] == arr[i + 1]) return false ; modify++; } } // Check whether the last element needs // to be modify or not if (arr[n - 1] < arr[n - 2]) modify++; // If more than 1 modification is required if (modify > 1) return false ; return true ; } // Driver code int main() { int arr[] = { 2, 4, 8, 6, 9, 12 }; int n = sizeof (arr) / sizeof (arr[0]); if (check(arr, n)) cout << "Yes" << endl; else cout << "No" << endl; return 0; } |
Java
// Java implementation of the approach class GFG { // Function that returns true if arr[] // can be made strictly increasing after // modifying at most one element static boolean check( int arr[], int n) { // To store the number of modifications // required to make the array // strictly increasing int modify = 0 ; // Check whether the first element needs // to be modify or not if (arr[ 0 ] > arr[ 1 ]) { arr[ 0 ] = arr[ 1 ] / 2 ; modify++; } // Loop from 2nd element to the 2nd last element for ( int i = 1 ; i < n - 1 ; i++) { // Check whether arr[i] needs to be modified if ((arr[i - 1 ] < arr[i] && arr[i + 1 ] < arr[i]) || (arr[i - 1 ] > arr[i] && arr[i + 1 ] > arr[i])) { // Modifying arr[i] arr[i] = (arr[i - 1 ] + arr[i + 1 ]) / 2 ; // Check if arr[i] is equal to any of // arr[i-1] or arr[i+1] if (arr[i] == arr[i - 1 ] || arr[i] == arr[i + 1 ]) return false ; modify++; } } // Check whether the last element needs // to be modify or not if (arr[n - 1 ] < arr[n - 2 ]) modify++; // If more than 1 modification is required if (modify > 1 ) return false ; return true ; } // Driver code public static void main(String[] args) { int [] arr = { 2 , 4 , 8 , 6 , 9 , 12 }; int n = arr.length; if (check(arr, n)) System.out.print( "Yes" ); else System.out.print( "No" ); } } |
C#
// C# implementation of the approach using System; class GFG { // Function that returns true if arr[] // can be made strictly increasing after // modifying at most one element static bool check( int []arr, int n) { // To store the number of modifications // required to make the array // strictly increasing int modify = 0; // Check whether the first element needs // to be modify or not if (arr[0] > arr[1]) { arr[0] = arr[1] / 2; modify++; } // Loop from 2nd element to the 2nd last element for ( int i = 1; i < n - 1; i++) { // Check whether arr[i] needs to be modified if ((arr[i - 1] < arr[i] && arr[i + 1] < arr[i]) || (arr[i - 1] > arr[i] && arr[i + 1] > arr[i])) { // Modifying arr[i] arr[i] = (arr[i - 1] + arr[i + 1]) / 2; // Check if arr[i] is equal to any of // arr[i-1] or arr[i+1] if (arr[i] == arr[i - 1] || arr[i] == arr[i + 1]) return false ; modify++; } } // Check whether the last element needs // to be modify or not if (arr[n - 1] < arr[n - 2]) modify++; // If more than 1 modification is required if (modify > 1) return false ; return true ; } // Driver code public static void Main() { int [] arr = { 2, 4, 8, 6, 9, 12 }; int n = arr.Length; if (check(arr, n)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by AnkitRai01 |
Python 3
# Python 3 implementation of above approach # Function that returns true if arr[] # can be made strictly increasing after # modifying at most one element def check( arr, n): # To store the number of modifications # required to make the array # strictly increasing modify = 0 # Check whether the first element needs # to be modify or not if (arr[ 0 ] > arr[ 1 ]) : arr[ 0 ] = arr[ 1 ] / / 2 modify + = 1 # Loop from 2nd element to the 2nd last element for i in range ( 1 , n - 1 ): # Check whether arr[i] needs to be modified if ((arr[i - 1 ] < arr[i] and arr[i + 1 ] < arr[i]) or (arr[i - 1 ] > arr[i] and arr[i + 1 ] > arr[i])): # Modifying arr[i] arr[i] = (arr[i - 1 ] + arr[i + 1 ]) / / 2 # Check if arr[i] is equal to any of # arr[i-1] or arr[i+1] if (arr[i] = = arr[i - 1 ] or arr[i] = = arr[i + 1 ]): return False modify + = 1 # Check whether the last element needs # to be modify or not if (arr[n - 1 ] < arr[n - 2 ]): modify + = 1 # If more than 1 modification is required if (modify > 1 ): return False return True # Driver code if __name__ = = "__main__" : arr = [ 2 , 4 , 8 , 6 , 9 , 12 ] n = len (arr) if (check(arr, n)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by ChitraNayal |
Javascript
<script> // Javascript implementation of the approach // Function that returns true if arr[] // can be made strictly increasing after // modifying at most one element function check(arr, n) { // To store the number of modifications // required to make the array // strictly increasing var modify = 0; // Check whether the first element needs // to be modify or not if (arr[0] > arr[1]) { arr[0] = arr[1] / 2; modify++; } // Loop from 2nd element to the 2nd last element for ( var i = 1; i < n - 1; i++) { // Check whether arr[i] needs to be modified if ((arr[i - 1] < arr[i] && arr[i + 1] < arr[i]) || (arr[i - 1] > arr[i] && arr[i + 1] > arr[i])) { // Modifying arr[i] arr[i] = (arr[i - 1] + arr[i + 1]) / 2; // Check if arr[i] is equal to any of // arr[i-1] or arr[i+1] if (arr[i] == arr[i - 1] || arr[i] == arr[i + 1]) return false ; modify++; } } // Check whether the last element needs // to be modify or not if (arr[n - 1] < arr[n - 2]) modify++; // If more than 1 modification is required if (modify > 1) return false ; return true ; } // Driver code var arr = [ 2, 4, 8, 6, 9, 12 ]; var n = arr.length; if (check(arr, n)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by noob2000. </script> |
Yes
Time Complexity: O(n)
Auxiliary Space: O(1)