Horje
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>

 
 

Output

Hidden: 7
Missing: 5

 

Time Complexity: O(N)

 

Auxiliary Space: O(N)

 


 


Reffered: https://www.geeksforgeeks.org

Arrays

Related
Reduce the Array to 0 by decreasing elements by 1 or replacing at most K elements by 0 Reduce the Array to 0 by decreasing elements by 1 or replacing at most K elements by 0
Count of pairs in Array with difference equal to the difference with digits reversed Count of pairs in Array with difference equal to the difference with digits reversed
Longest non-decreasing subsequence having difference between adjacent elements less than D Longest non-decreasing subsequence having difference between adjacent elements less than D
Java Program to Inplace rotate square matrix by 90 degrees | Set 1 Java Program to Inplace rotate square matrix by 90 degrees | Set 1
PHP Program to Find Maximum Value of Sum ( i*arr[i]) with Only Rotations on Given Array Allowed PHP Program to Find Maximum Value of Sum ( i*arr[i]) with Only Rotations on Given Array Allowed

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 9



 

Horje