Find the missing value from Array B formed by adding some value X to Array A
Given two arrays arr1[] and arr2[] of size N and N – 1 respectively. Each value in arr2[] is obtained by adding a hidden value say X to any arr1[i] for N-1 times, which means for any i, arr1[i]+X is not included in arr2[] that is the missing value in arr2[]. The task is to find both the hidden value X and the missing value which is not picked from arr1[].
Examples:
Input: arr1[] = {3, 6, 5, 10}, arr2[] = {17, 10, 13}
Output: Hidden = 7, Missing = 5
Explanation: The elements of the second array are obtained in the following way:
First element: (10 + 7) = 17, 10 is the element at index 4 of arr1[]
Second element: (3 + 7) = 10, 3 is the element at index 0 of arr1[]
Third element: (6 + 7) = 13, 6 is the element at index 1 of arr1[]
So, 7 is the hidden value and 5 is the missing value.Input: arr1[] = {4, 1, 7}, arr2[] = {4, 10}
Output: Hidden = 3, Missing = 4
Approach: This problem can be solved by using
- Sort both the given arrays in non-decreasing order.
- Create an unordered map to store differences.
- Traverse the arrays till N – 1 and check for the values by storing the differences of elements of both the arrays.
- Let a = arr2[i] – arr1[i] and b = arr2[i] – arr1[i+1].
- If a!=b then check if
- a > 0, then store it in map.
- b > 0, then store it in map.
- else check if a > 0, then store it in map.
- Iterate over the map and find the hidden value and print it.
- Traverse arr1[] by adding the hidden value and check if it is present in arr2[], else print the missing value.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the hidden // and missing values void findHiddenMissing( int arr1[], int arr2[], int N) { // Sorting both the arrays sort(arr1, arr1 + N); sort(arr2, arr2 + N - 1); // Create a map unordered_map< int , int > mp; // Traversing the arrays and // checking for the values for ( int i = 0; i < N - 1; i++) { // Variable to store the difference // between the elements of arr2 // and arr1 in same indices int a = arr2[i] - arr1[i]; // Variable to store the difference // between the elements of arr2 // and arr1 next index int b = arr2[i] - arr1[i + 1]; // If a is not equals to b if (a != b) { // If a is greater than 0 if (a > 0) mp[a] += 1; // If b is greater than 0 if (b > 0) mp[b] += 1; } // If a is equal to b else { // If a is greater than 0 if (a > 0) mp[a] += 1; } } // To store the hidden value int hidden; // Iterate over the map and searching // for the hidden value for ( auto it : mp) { if (it.second == N - 1) { hidden = it.first; cout << "Hidden: " << it.first; break ; } } cout << endl; // Find the missing value for ( int i = 0; i < N; i++) { if (arr1[i] + hidden != arr2[i]) { cout << "Missing: " << arr1[i]; break ; } } } // Driver Code int main() { int arr1[] = { 3, 6, 5, 10 }; int arr2[] = { 17, 10, 13 }; int N = sizeof (arr1) / sizeof (arr1[0]); findHiddenMissing(arr1, arr2, N); return 0; } |
Java
// Java program for the above approach import java.util.Arrays; import java.util.HashMap; class GFG { // Function to find the hidden // and missing values public static void findHiddenMissing( int arr1[], int arr2[], int N) { // Sorting both the arrays Arrays.sort(arr1); Arrays.sort(arr2); // Create a map HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); // Traversing the arrays and // checking for the values for ( int i = 0 ; i < N - 1 ; i++) { // Variable to store the difference // between the elements of arr2 // and arr1 in same indices int a = arr2[i] - arr1[i]; // Variable to store the difference // between the elements of arr2 // and arr1 next index int b = arr2[i] - arr1[i + 1 ]; // If a is not equals to b if (a != b) { // If a is greater than 0 if (a > 0 ) { if (mp.containsKey(a)) mp.put(a, mp.get(a) + 1 ); else mp.put(a, 1 ); } // If b is greater than 0 if (b > 0 ) if (mp.containsKey(b)) mp.put(b, mp.get(b) + 1 ); else mp.put(b, 1 ); } // If a is equal to b else { // If a is greater than 0 if (a > 0 ) if (mp.containsKey(a)) mp.put(a, mp.get(a) + 1 ); else mp.put(a, 1 ); } } // To store the hidden value int hidden = 0 ; // Iterate over the map and searching // for the hidden value for ( int it : mp.keySet()) { if (mp.get(it) == N - 1 ) { hidden = it; System.out.println( "Hidden: " + it); break ; } } // Find the missing value for ( int i = 0 ; i < N; i++) { if (arr1[i] + hidden != arr2[i]) { System.out.println( "Missing: " + arr1[i]); break ; } } } // Driver Code public static void main(String args[]) { int arr1[] = { 3 , 6 , 5 , 10 }; int arr2[] = { 17 , 10 , 13 }; int N = arr1.length; findHiddenMissing(arr1, arr2, N); } } // This code is contributed by saurabh_jaiswal. |
Python3
# python program for the above approach # Function to find the hidden # and missing values def findHiddenMissing(arr1, arr2, N): # Sorting both the arrays arr1.sort() arr2.sort() # Create a map mp = {} # Traversing the arrays and # checking for the values for i in range ( 0 , N - 1 ): # Variable to store the difference # between the elements of arr2 # and arr1 in same indices a = arr2[i] - arr1[i] # Variable to store the difference # between the elements of arr2 # and arr1 next index b = arr2[i] - arr1[i + 1 ] # If a is not equals to b if (a ! = b): # If a is greater than 0 if (a > 0 ): if not a in mp: mp[a] = 1 else : mp[a] + = 1 # If b is greater than 0 if (b > 0 ): if not b in mp: mp[b] = 1 else : mp[b] + = 1 # If a is equal to b else : # If a is greater than 0 if (a > 0 ): if not a in mp: mp[a] = 1 else : mp[a] + = 1 # To store the hidden value hidden = 0 # Iterate over the map and searching # for the hidden value for it in mp: if (mp[it] = = N - 1 ): hidden = it print ( "Hidden:" , end = " " ) print (it) break # Find the missing value for i in range ( 0 , N): if (arr1[i] + hidden ! = arr2[i]): print ( "Missing:" , end = " " ) print (arr1[i]) break # Driver Code if __name__ = = "__main__" : arr1 = [ 3 , 6 , 5 , 10 ] arr2 = [ 17 , 10 , 13 ] N = len (arr1) findHiddenMissing(arr1, arr2, N) # This code is contributed by rakeshsahni |
C#
// C# program for the above approach using System; using System.Collections; using System.Collections.Generic; class GFG { // Function to find the hidden // and missing values public static void findHiddenMissing( int []arr1, int []arr2, int N) { // Sorting both the arrays Array.Sort(arr1); Array.Sort(arr2); // Create a map Dictionary< int , int > mp = new Dictionary< int , int >(); // Traversing the arrays and // checking for the values for ( int i = 0; i < N - 1; i++) { // Variable to store the difference // between the elements of arr2 // and arr1 in same indices int a = arr2[i] - arr1[i]; // Variable to store the difference // between the elements of arr2 // and arr1 next index int b = arr2[i] - arr1[i + 1]; // If a is not equals to b if (a != b) { // If a is greater than 0 if (a > 0) { if (mp.ContainsKey(a)) mp[a] = mp[a] + 1; else mp.Add(a, 1); } // If b is greater than 0 if (b > 0) if (mp.ContainsKey(b)) mp[b] = mp[b] + 1; else mp.Add(b, 1); } // If a is equal to b else { // If a is greater than 0 if (a > 0) if (mp.ContainsKey(a)) mp[a] = mp[a] + 1; else mp.Add(a, 1); } } // To store the hidden value int hidden = 0; // Iterate over the map and searching // for the hidden value foreach ( int it in mp.Keys) { if (mp[it] == N - 1) { hidden = it; Console.WriteLine( "Hidden: " + it); break ; } } // Find the missing value for ( int i = 0; i < N; i++) { if (arr1[i] + hidden != arr2[i]) { Console.WriteLine( "Missing: " + arr1[i]); break ; } } } // Driver Code public static void Main( string []args) { int []arr1 = { 3, 6, 5, 10 }; int []arr2 = { 17, 10, 13 }; int N = arr1.Length; findHiddenMissing(arr1, arr2, N); } } // This code is contributed by rutvik_56. |
Javascript
<script> // Javascript program for the above approach // Function to find the hidden // and missing values function findHiddenMissing(arr1, arr2, N) { // Sorting both the arrays arr1.sort((a, b) => a - b); arr2.sort((a, b) => a - b); // Create a map let mp = new Map(); // Traversing the arrays and // checking for the values for (let i = 0; i < N - 1; i++) { // Variable to store the difference // between the elements of arr2 // and arr1 in same indices let a = arr2[i] - arr1[i]; // Variable to store the difference // between the elements of arr2 // and arr1 next index let b = arr2[i] - arr1[i + 1]; // If a is not equals to b if (a != b) { // If a is greater than 0 if (a > 0) { if (mp.has(a)) { mp.set(a, mp.get(a) + 1); } else { mp.set(a, 1); } } // If b is greater than 0 if (b > 0) if (mp.has(b)) { mp.set(b, mp.get(b) + 1); } else { mp.set(b, 1); } } // If a is equal to b else { // If a is greater than 0 if (a > 0) { if (mp.has(a)) { mp.set(a, mp.get(a) + 1); } else { mp.set(a, 1); } } } } // To store the hidden value let hidden; // Iterate over the map and searching // for the hidden value for (let it of mp) { if (it[1] == N - 1) { hidden = it[0]; document.write( "Hidden: " + it[0]); break ; } } document.write( "<br>" ); // Find the missing value for (let i = 0; i < N; i++) { if (arr1[i] + hidden != arr2[i]) { document.write( "Missing: " + arr1[i]); break ; } } } // Driver Code let arr1 = [3, 6, 5, 10]; let arr2 = [17, 10, 13]; let N = arr1.length; findHiddenMissing(arr1, arr2, N); // This code is contributed by saurabh_jaiswal. </script> |
Hidden: 7 Missing: 5
Time Complexity: O(N)
Auxiliary Space: O(N)