Given an array arr[] of N positive integers, the task is to check whether an array can be made strictly increasing by shifting 1 value to its right element any number of times (i.e, for any value of i, decrement arr[i] and increment arr[i + 1] by 1).
Note: The integer at any index after any operation must not be negative.
Example:
Input: arr[] = {4, 5, 4}
Output: Yes
Explanation: The array can be made strictly increasing by performing the following operations:
- Choose i = 1 and shift value 1 from A1 to A2 . Now, arr[] = {3, 6, 4}.
- Choose i = 2 and shift value 1 from A2 to A3 . Now, arr[] = {3, 5, 5}.
- Choose i = 2 and shift value 1 from A2 to A3 . Now, arr[] = {3, 4, 6}.
Input: arr[] = {0, 1, 0}
Output: No
Approach: The given problem can be solved using a greedy approach. The idea is that for any index i, the least possible strictly increasing sequence without including the negative integers is 0, 1, 2, 3, … . Hence, for each value of i in the range [0, N), the sum of integers till arr[i] must be greater than the sum of the series 0, 1, 2, …, i-1 which is equivalent to (i * (i – 1))/2. Therefore, if the given array satisfies that condition, return “Yes“, otherwise, return “No“.
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <iostream>using namespace std;// Function to check whether the given// array can be made strictly increasing// by shifting 1 value to the rightbool isPossible(int arr[], int N){ // Stores the sum of arr[] int sum = 0; // Loop to traverse the array for (int i = 0; i < N; i++) { // Update sum sum += arr[i]; // If sum is less than the // least required value if (sum < i * (i + 1) / 2) return false; } // Return possible return true;}// Driver Codeint main(){ int arr[] = { 4, 5, 4 }; int N = sizeof(arr) / sizeof(int); if (isPossible(arr, N)) { cout << "Yes"; } else { cout << "No"; } return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{ // Function to check whether the given // array can be made strictly increasing // by shifting 1 value to the right static Boolean isPossible(int arr[], int N) { // Stores the sum of arr[] int sum = 0; // Loop to traverse the array for (int i = 0; i < N; i++) { // Update sum sum += arr[i]; // If sum is less than the // least required value if (sum < i * (i + 1) / 2) return false; } // Return possible return true; } public static void main (String[] args) { int arr[] = { 4, 5, 4 }; int N = arr.length; if (isPossible(arr, N)) { System.out.print("Yes"); } else { System.out.print("No"); } }}// This code is contributed by hrithikgarg03188 |
Python3
# Python code for the above approach# Function to check whether the given# array can be made strictly increasing# by shifting 1 value to the rightdef isPossible(arr, N): # Stores the sum of arr[] sum = 0 # Loop to traverse the array for i in range(N): # Update sum sum += arr[i] # If sum is less than the # least required value if sum < i * (i + 1) / 2: return 0 # Return possible return 1# Driver Codearr = [4, 5, 4]N = len(arr)if isPossible(arr, N) == 1: print("Yes")else: print("No") # This code is contributed by Potta Lokesh |
C#
// C# program for the above approachusing System;class GFG{ // Function to check whether the given // array can be made strictly increasing // by shifting 1 value to the right static Boolean isPossible(int []arr, int N) { // Stores the sum of arr[] int sum = 0; // Loop to traverse the array for (int i = 0; i < N; i++) { // Update sum sum += arr[i]; // If sum is less than the // least required value if (sum < i * (i + 1) / 2) return false; } // Return possible return true; } public static void Main () { int []arr = { 4, 5, 4 }; int N = arr.Length; if (isPossible(arr, N)) { Console.Write("Yes"); } else { Console.Write("No"); } }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// Javascript program of the above approach// Function to check whether the given// array can be made strictly increasing// by shifting 1 value to the rightfunction isPossible(arr, N) { // Stores the sum of arr[] let sum = 0; // Loop to traverse the array for (let i = 0; i < N; i++) { // Update sum sum += arr[i]; // If sum is less than the // least required value if (sum < i * (i + 1) / 2) return false; } // Return possible return true;}// Driver Codelet arr = [4, 5, 4];let N = arr.length;if (isPossible(arr, N)) { document.write("Yes");}else { document.write("No");}// This code is contributed by gfgking.</script> |
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
