Horje
Check if Array can be made strictly increasing by replacing element with Average of adjacents

Given an array A[] of size N, the task is to check whether the sequence can be made strictly increasing by performing the following operation any number of times(0 or more): 

  • Select any two adjacent elements Ai and Ai+1 and replace one of them with (Ai + Ai+1) / 2 (a real number, i.e. without rounding).

Examples:

Input: A[] = {1, 2, 2}
Output: Yes

Explanation: Choose A0 and A1 and change A1 to (1 + 2) / 2 = 1.5. 
The sequence after this operation is [1, 1.5, 2], which is a strictly increasing order.

Input: A[] = {7, 4}
Output: No

Approach: The problem can be solved based on the following observation:

  • If the given sequence is in decreasing order, then it is never possible to make a sequence in strictly increasing order.
  • In all other cases, it is always possible.

Follow the below steps to implement the above idea:

  • Check if there exists any pair such that Ai < Ai+1, then it is always possible to make the given sequence in strictly increasing order.
  • Otherwise, the sequence is in decreasing order. 
  • Hence when the sequence is in decreasing order, it will be never possible to make the sequence in strictly increasing order.

Below is the implementation of the above approach.

C++

#include <iostream>
using namespace std;
 
// Function to check whether sequence
// can be in strictly increasing order
string check(int A[], int N)
{
    bool good = false;
    for (int i = 0; i < N - 1; i++) {
        if (A[i] < A[i + 1])
            good = true;
    }
    if (good)
        return "Yes";
    return "No";
}
 
// Driver code
int main()
{
 
    int A[] = { 1, 2, 2 };
    int N = sizeof(A) / sizeof(A[0]);
    // Function call
    cout << check(A, N);
    return 0;
}
 
// This code is contributed by aarohirai2616.

Java

// Java code to implement the approach
 
import java.io.*;
import java.util.*;
 
public class GFG {
 
    // Function to check whether sequence
    // can be in strictly increasing order
    public static String check(int A[], int N)
    {
        boolean good = false;
        for (int i = 0; i < N - 1; i++) {
            if (A[i] < A[i + 1])
                good = true;
        }
        if (good)
            return "Yes";
        return "No";
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int A[] = { 1, 2, 2 };
        int N = A.length;
 
        // Function call
        System.out.println(check(A, N));
    }
}

Python3

# Python3 code to implement the approach
 
# Function to check whether sequence
# can be in strictly increasing order
def check(A, N):
    good = False
    for i in range(0, N-1):
        if (A[i] < A[i + 1]):
            good = True
 
    if (good):
        return "Yes"
    return "No"
 
# Driver Code
if __name__ == '__main__':
    A = [1, 2, 2]
    N = len(A)
 
   # Function call
    print(check(A, N))
 
    # This code is contributed by aarohirai2616.

C#

// C# code to implement the approach
using System;
public class GFG {
 
  // Function to check whether sequence
  // can be in strictly increasing order
  public static String check(int []A, int N)
  {
    bool good = false;
    for (int i = 0; i < N - 1; i++) {
      if (A[i] < A[i + 1])
        good = true;
    }
    if (good)
      return "Yes";
    return "No";
  }
 
  // Driver code
  public static void Main(string[] args)
  {
    int []A = { 1, 2, 2 };
    int N = A.Length;
 
    // Function call
    Console.WriteLine(check(A, N));
  }
}
 
// This code is contributed by AnkThon

Javascript

<script>
// Javascript code to implement the approach
 
// Function to check whether sequence
 // can be in strictly increasing order
function check(A,N)
{
     let good = false;
        for (let i = 0; i < N - 1; i++) {
            if (A[i] < A[i + 1])
                good = true;
        }
        if (good)
            return "Yes";
        return "No";
}
 
// Driver code
 let A = [ 1, 2, 2 ];
        let N = A.length;
 
        // Function call
        console.log(check(A, N));
         
        // This code is contributed by aarohirai2616.
</script>

Output

Yes

Time Complexity: O(N) 
Auxiliary Space: O(1)


 


Reffered: https://www.geeksforgeeks.org

Arrays

Related
Lexicographical smallest and largest Permutation from Array whose elements are max of Prefix Lexicographical smallest and largest Permutation from Array whose elements are max of Prefix
Minimize Array sum by replacing an element with GCD Minimize Array sum by replacing an element with GCD
Minimize operations to empty Array by deleting two unequal elements or one element Minimize operations to empty Array by deleting two unequal elements or one element
Count ways to make given Subarray strictly increasing by replacing one element for Q queries Count ways to make given Subarray strictly increasing by replacing one element for Q queries
Find the MEX of given Array Find the MEX of given Array

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 13



 

Horje