Minimum change in given value so that it lies in all given Ranges
Given an array of ranges arr[] of length N and a number D, the task is to find the minimum amount by which the number D should be changed such that D lies in every range of given array. Here a range consists of two integer [start, end] and D is said to be inside of range, if start ? D ? end.
Examples:
Input: N = 3, D = 3
arr[] = {{0, 7}, {2, 14}, {4, 6}}
Output: 1
Explanation:
Here if we increment D by 1 then it will be inside of every range that is start ? D ? end.Input: N = 2, D = 2
arr[] = {{1, 2}, {3, 2}}
Output: 0
Explanation:
Here D = 2 which is already inside of every range that is start ? D ? end.
Approach:
- Iterate over the array of ranges and to find the maximum value of the start[i] and the minimum value of the end[i] where the final max_start and min_end will show the common range of the given array of ranges.
- Check that D is already inside of the max_start and the min_end computed.
- If D is already inside of the range, then the minimum difference is 0.
- Else find the nearest value to D out of max_start and min_end that is
min(abs(D - max_start), abs(D - min_end))
Below is the code of the above approach:
C++
// C++ implementation find the minimum // difference in the number D such that // D is inside of every range #include <bits/stdc++.h> using namespace std; // Function to find the minimum // difference in the number D such that // D is inside of every range void findMinimumOperation( int n, int d, int arrays[3][2]){ int cnt = 0; int first = INT_MIN, end = INT_MAX; // Loop to find the common range out // of the given array of ranges. while (n--) { // Storing the start and end index int arr[2] = { arrays[cnt][0], arrays[cnt][1] }; // Sorting the range sort(arr, arr + 2); // Finding the maximum starting // value of common segment first = max(first, arr[0]); // Finding the minimum ending // value of common segment end = min(end, arr[1]); cnt++; } // If there is no common segment if (first > end) cout << "-1" ; else { // If the given number is between // the computed common range. if (d >= first && d <= end) { cout << "0" ; } // Finding the minimum distance else cout << min( abs (first - d), abs (d - end)); } } // Driver Code int main() { int n = 3, d = 3; // Given array of ranges int arrays[3][2] = { { 0, 7 }, { 2, 14 }, { 4, 6 } }; findMinimumOperation(n, d, arrays); } |
Java
// Java implementation find the minimum // difference in the number D such that // D is inside of every range import java.util.*; class GFG { // Function to find the minimum // difference in the number D such that // D is inside of every range static void findMinimumOperation( int n, int d, int arrays[][]){ int cnt = 0 ; int first = Integer.MIN_VALUE, end = Integer.MAX_VALUE; // Loop to find the common range out // of the given array of ranges. while (n > 0 ) { // Storing the start and end index int arr[] = { arrays[cnt][ 0 ], arrays[cnt][ 1 ] }; // Sorting the range Arrays.sort(arr); // Finding the maximum starting // value of common segment first = Math.max(first, arr[ 0 ]); // Finding the minimum ending // value of common segment end = Math.min(end, arr[ 1 ]); cnt++; n--; } // If there is no common segment if (first > end) System.out.print( "-1" ); else { // If the given number is between // the computed common range. if (d >= first && d <= end) { System.out.print( "0" ); } // Finding the minimum distance else System.out.print(Math.min(Math.abs(first - d), Math.abs(d - end))); } } // Driver Code public static void main (String []args) { int n = 3 , d = 3 ; // Given array of ranges int arrays[][] = { { 0 , 7 }, { 2 , 14 }, { 4 , 6 } }; findMinimumOperation(n, d, arrays); } } // This code is contributed by chitranayal |
Python3
# Python3 implementation find the minimum # difference in the number D such that # D is inside of every range # Function to find the minimum # difference in the number D such that # D is inside of every range def findMinimumOperation(n, d,arrays): cnt = 0 first = - 10 * * 9 end = 10 * * 9 # Loop to find the common range out # of the given array of ranges. while (n): # Storing the start and end index arr = [arrays[cnt][ 0 ],arrays[cnt][ 1 ]] # Sorting the range arr = sorted (arr) # Finding the maximum starting # value of common segment first = max (first, arr[ 0 ]) # Finding the minimum ending # value of common segment end = min (end, arr[ 1 ]) cnt + = 1 n - = 1 # If there is no common segment if (first > end): print ( "-1" ,end = "") else : # If the given number is between # the computed common range. if (d > = first and d < = end): print ( "0" ,end = "") # Finding the minimum distance else : print ( min ( abs (first - d), abs (d - end)),end = "") # Driver Code if __name__ = = '__main__' : n = 3 d = 3 # Given array of ranges arrays = [[ 0 , 7 ], [ 2 , 14 ], [ 4 , 6 ] ] findMinimumOperation(n, d, arrays) # This code is contributed by mohit kumar 29 |
C#
// C# implementation find the minimum // difference in the number D such that // D is inside of every range using System; class GFG { // Function to find the minimum // difference in the number D such that // D is inside of every range static void findMinimumOperation( int n, int d, int [,]arrays){ int cnt = 0; int first = int .MinValue, end = int .MaxValue; // Loop to find the common range out // of the given array of ranges. while (n > 0) { // Storing the start and end index int []arr = { arrays[cnt, 0], arrays[cnt, 1] }; // Sorting the range Array.Sort(arr); // Finding the maximum starting // value of common segment first = Math.Max(first, arr[0]); // Finding the minimum ending // value of common segment end = Math.Min(end, arr[1]); cnt++; n--; } // If there is no common segment if (first > end) Console.Write( "-1" ); else { // If the given number is between // the computed common range. if (d >= first && d <= end) { Console.Write( "0" ); } // Finding the minimum distance else Console.Write(Math.Min(Math.Abs(first - d), Math.Abs(d - end))); } } // Driver Code public static void Main(String []args) { int n = 3, d = 3; // Given array of ranges int [,]arrays = { { 0, 7 }, { 2, 14 }, { 4, 6 } }; findMinimumOperation(n, d, arrays); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript implementation find the minimum // difference in the number D such that // D is inside of every range // Function to find the minimum // difference in the number D such that // D is inside of every range function findMinimumOperation(n, d, arrays) { var cnt = 0; var first = Number.MIN_VALUE, end = Number.MAX_VALUE; // Loop to find the common range out // of the given array of ranges. while (n > 0) { // Storing the start and end index var arr = [arrays[cnt][0], arrays[cnt][1]]; // Sorting the range arr.sort((a, b) => a - b); // Finding the maximum starting // value of common segment first = Math.max(first, arr[0]); // Finding the minimum ending // value of common segment end = Math.min(end, arr[1]); cnt++; n--; } // If there is no common segment if (first > end) document.write( "-1" ); else { // If the given number is between // the computed common range. if (d >= first && d <= end) { document.write( "0" ); } // Finding the minimum distance else document.write(Math.min( Math.abs(first - d), Math.abs(d - end))); } } // Driver Code var n = 3, d = 3; // Given array of ranges var arrays = [ [ 0, 7 ], [ 2, 14 ], [ 4, 6 ] ]; findMinimumOperation(n, d, arrays); // This code is contributed by Rajput-Ji </script> |
1
Time complexity: O((n^2)*logn) because sort function is being used in while loop
Auxiliary space: O(1)