Discover the worth of Okay after changing each index of the array by |ai – Okay|

Given an array, arr[] containing n integers, the duty is to seek out an integer (say Okay) such that after changing every index of the array by |a_i  – Okay| the place ( i ∈ [1, n]), ends in a sorted array. If no such integer exists that satisfies the above situation then return -1.

Examples:

Enter: arr[ ] = [10, 5, 4, 3, 2, 1]
Output: 8
Clarification: Upon performing the operation |a_i-8|, we get [2, 3, 4, 5, 6, 7] which is sorted.

Enter: arr[ ] = [1, 2, 3, 4, 5, 6] 
Output: 0
Clarification: Because the array is already sorted so the worth of Okay can be 0 on this case.

Strategy: The issue may be solved based mostly on the next commentary:

Observations:

For the array to be sorted every pair of adjoining parts must be sorted. Meaning few instances come up if we take look after specific a_i and a_i+1 and people are as follows:

• Let (a_i < a_i+1 ), so the next inequality come up: 
  • If (Okay ≤a_i) then upon  (a_i – Okay ≤ a_i+1 – Okay) the weather shall be as it’s (a_i < a_i+1).
  • If (Okay ≥ a_i) then upon  ( Okay – a_i ≤ Okay – a_i+1 ) the weather shall be as it’s (ai > a_i+1).
  • So, Okay must be halfway between a_i and a_i+1 that’s Okay must be Okay ≤ (a_i + a_i+1)/2 .
• Equally for (a_i > a_i+1) the worth of ok can be Okay ≥ (a_i + a_i+1)/2 
• Lastly we’ll take the minimal of all for which (Okay < a_i) and most of all for which (Okay > a_i).

Comply with the steps talked about beneath to implement the thought:

• Initialize two variables l and r for the 2 values of ok defined above.
• Iterate over the array and verify if (a_i < a_i+1) then retailer in r the minimal of r up to now and the current worth of Okay.
• Else if, (a_i > a_i+1) shops it in l the utmost of l up to now and the current worth of Okay.
• Lastly if (l > r) return -1;
• Else, return l 

Under is the Implementation of the above method: 

// C++ code for the above method:
#embody <bits/stdc++.h>
utilizing namespace std;

// Perform to seek out Okay
void findk(int a[], int n)
{

    // Initializing the 2 variables
    int l = 0, r = 1e9;

    for (int i = 0; i < n - 1; i++) {

        // If (a[i] < a[i+1]) then take
        // mimimum and retailer in variable

        if (a[i] < a[i + 1]) {
            r = min(r, (a[i] + a[i + 1]) / 2);
        }

        // If (a[i]>a[i+1]) then take
        // most and retailer in
        // seperate variable
        else if (a[i] > a[i + 1]) {
            l = max(l, (a[i] + a[i + 1] + 1) / 2);
        }
    }

    if (l > r) {
        cout << "-1";
    }

    else

        cout << l << endl;
}

// Driver operate
int principal()
{
    int arr[] = { 10, 5, 4, 3, 2, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);

    // Perform Name
    findk(arr, n);
    return 0;
}

// Java Implementation

import java.util.*;

class GFG {
    public static void principal(String[] args)
    {
        int[] arr = { 10, 5, 4, 3, 2, 1 };
        int n = arr.size;
        discover(arr, n);
    }

    public static void discover(int[] arr, int n)
    {
        // Initializing the 2 variables
        int l = 0;
        int r = 1000000000;
        for (int i = 0; i < n - 1; i++) {

            // If (a[i]<a[i+1]) then take mimimum and retailer in variable)

            if (arr[i] < arr[i + 1]) {
                r = Math.min(r, (arr[i] + arr[i + 1]) / 2);
            }

            // If (a[i]>a[i+1]) then take most and retailer in seperate variable)

            else if (arr[i] > arr[i + 1]) {
                l = Math.max(l,
                             (arr[i] + arr[i + 1] + 1) / 2);
            }
        }

        if (l > r) {
            System.out.println(-1);
        }
        else {
            System.out.println(l);
        }
    }
}

Time Complexity: O(n), iterating the loop for as soon as solely.
Auxiliary House: O(1), no further house is used.