Given an array arr[] of some positive integers and missing occurrence of a specific integer represented by -1, the task is to find that missing number such that maximum absolute difference between adjacent elements is minimum.
Examples:
Input: arr[] = {-1, 10, -1, 12, -1}
Output: 11
Explanation:
Differences of Adjacent elements –
=> a[0] – a[1] = 11 – 10 = 1
=> a[2] – a[1] = 11 – 10 = 1
=> a[3] – a[2] = 12 – 11 = 1
=> a[3] – a[4] = 12 – 11 = 1
Maximum absolute difference of adjacent elements – 2
Input: arr[] = {1,-1, 7, 5, 2, -1, 5}
Output: 4
Explanation:
Differences of Adjacent elements –
=> a[1] – a[0] = 4 – 1 = 3
=> a[2] – a[1] = 7 – 4 = 3
=> a[2] – a[3] = 7 – 5 = 2
=> a[3] – a[4] = 5 – 2 = 3
=> a[5] – a[4] = 4 – 2 = 2
=> a[6] – a[5] = 5 – 4 = 1
Maximum absolute difference of adjacent elements – 3
Approach: The idea is to find the maximum and minimum adjacent element to the missing number and the missing number can be the average of these two values such that maximum absolute difference is minimum.
=> max = Maximum adjacent element => min = Minimum adjacent element Missing number = (max + min) ------------- 2
Below is the implementation of the above approach:
C++
// C++ implementation of the missing // number such that maximum absolute // difference between adjacent element // is minimum #include <bits/stdc++.h> using namespace std; // Function to find the missing // number such that maximum // absolute difference is minimum int missingnumber( int n, int arr[]) { int mn = INT_MAX, mx = INT_MIN; // Loop to find the maximum and // minimum adjacent element to // missing number for ( int i = 0; i < n; i++) { if (i > 0 && arr[i] == -1 && arr[i - 1] != -1) { mn = min(mn, arr[i - 1]); mx = max(mx, arr[i - 1]); } if (i < (n - 1) && arr[i] == -1 && arr[i + 1] != -1) { mn = min(mn, arr[i + 1]); mx = max(mx, arr[i + 1]); } } long long int res = (mx + mn) / 2; return res; } // Driver Code int main() { int n = 5; int arr[5] = { -1, 10, -1, 12, -1 }; int ans = 0; // Function Call int res = missingnumber(n, arr); cout << res; return 0; } |
Java
// Java implementation of the missing // number such that maximum absolute // difference between adjacent element // is minimum import java.util.*; class GFG{ // Function to find the missing // number such that maximum // absolute difference is minimum static int missingnumber( int n, int arr[]) { int mn = Integer.MAX_VALUE, mx = Integer.MIN_VALUE; // Loop to find the maximum and // minimum adjacent element to // missing number for ( int i = 0 ; i < n; i++) { if (i > 0 && arr[i] == - 1 && arr[i - 1 ] != - 1 ) { mn = Math.min(mn, arr[i - 1 ]); mx = Math.max(mx, arr[i - 1 ]); } if (i < (n - 1 ) && arr[i] == - 1 && arr[i + 1 ] != - 1 ) { mn = Math.min(mn, arr[i + 1 ]); mx = Math.max(mx, arr[i + 1 ]); } } int res = (mx + mn) / 2 ; return res; } // Driver Code public static void main(String[] args) { int n = 5 ; int arr[] = { - 1 , 10 , - 1 , 12 , - 1 }; // Function Call int res = missingnumber(n, arr); System.out.print(res); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the missing # number such that maximum absolute # difference between adjacent element # is minimum import sys # Function to find the missing # number such that maximum # absolute difference is minimum def missingnumber(n, arr) - > int : mn = sys.maxsize; mx = - sys.maxsize - 1 ; # Loop to find the maximum and # minimum adjacent element to # missing number for i in range (n): if (i > 0 and arr[i] = = - 1 and arr[i - 1 ] ! = - 1 ): mn = min (mn, arr[i - 1 ]); mx = max (mx, arr[i - 1 ]); if (i < (n - 1 ) and arr[i] = = - 1 and arr[i + 1 ] ! = - 1 ): mn = min (mn, arr[i + 1 ]); mx = max (mx, arr[i + 1 ]); res = (mx + mn) / 2 ; return res; # Driver Code if __name__ = = '__main__' : n = 5 ; arr = [ - 1 , 10 , - 1 , 12 , - 1 ]; # Function call res = missingnumber(n, arr); print (res); # This code is contributed by amal kumar choubey |
C#
// C# implementation of the missing // number such that maximum absolute // difference between adjacent element // is minimum using System; class GFG{ // Function to find the missing // number such that maximum // absolute difference is minimum static int missingnumber( int n, int []arr) { int mn = Int32.MaxValue, mx = Int32.MinValue; // Loop to find the maximum and // minimum adjacent element to // missing number for ( int i = 0; i < n; i++) { if (i > 0 && arr[i] == -1 && arr[i - 1] != -1) { mn = Math.Min(mn, arr[i - 1]); mx = Math.Max(mx, arr[i - 1]); } if (i < (n - 1) && arr[i] == -1 && arr[i + 1] != -1) { mn = Math.Min(mn, arr[i + 1]); mx = Math.Max(mx, arr[i + 1]); } } int res = (mx + mn) / 2; return res; } // Driver Code public static void Main() { int n = 5; int []arr = new int []{ -1, 10, -1, 12, -1 }; // Function Call int res = missingnumber(n, arr); Console.WriteLine(res); } } // This code is contributed by Nidhi_biet |
Javascript
<script> // JavaScript implementation of the missing // number such that maximum absolute // difference between adjacent element // is minimum // Function to find the missing // number such that maximum // absolute difference is minimum function missingnumber(n, arr) { let mn = 10000; let mx = -10000; // Loop to find the maximum and // minimum adjacent element to // missing number for (let i = 0; i < n; i++) { if (i > 0 && arr[i] == -1 && arr[i - 1] != -1) { mn = Math.min(mn, arr[i - 1]); mx = Math.max(mx, arr[i - 1]); } if (i < (n - 1) && arr[i] == -1 && arr[i + 1] != -1) { mn = Math.min(mn, arr[i + 1]); mx = Math.max(mx, arr[i + 1]); } } let res = (mx + mn) / 2; return res; } // Driver Code let n = 5; let arr = [-1, 10, -1, 12, -1]; // Function Call let res = missingnumber(n, arr); document.write(res); </script> |
11
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!