Wednesday, March 8, 2023
HomeSoftware DevelopmentDiscover the worth of Okay after changing each index of the array...

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 |ai  – 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 |ai-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 ai and ai+1 and people are as follows:

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

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 (ai < ai+1) then retailer in r the minimal of r up to now and the current worth of Okay.
• Else if, (ai > ai+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++

```// 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

```// 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.

RELATED ARTICLES