CareerCup

findMissing(int a[],int b[]){ //O(n)
	return sum(a)-sum(b);
}

traverse both arrays at the same time, when you find an element in array 1 which is different or non-existant in array 2, return array1[i]. treat edge cases.

int findMissing(int a[], int b[]) {
  if (a.len < b.len || b.len != a.len-1) {
     return -1; // error
  }

   for (int i = 0; i < a.len; i ++) {
     if (i == b.len) {
       return a[a.len-1];
     } else if (i < b.len && a[i] != b[i]) {
       return a[i];
     }
   }

   return -1; // not found
}

Why not XOR all the elements of both arrays? a ^ a = 0, so the only item which is left out is the missing element.

import java.util.HashMap;


public class FindMissingandDuplicate {

static int flag=0;

public static void main(String[] args) {

int a[]={1,3,5,6,8};
int b[]={1,5,6,8};

FindMissingandDuplicate obj=new FindMissingandDuplicate();
obj.findMissing(a,b);

if(flag==0)
System.out.println("No missing number");
// TODO Auto-generated method stub

}

private static void findMissing(int[] a, int[] b) {
// TODO Auto-generated method stub
int len1=a.length;
int len2=b.length;

HashMap <Integer,Integer> map=new HashMap<Integer,Integer>();

if(len1<len2)
{
for(int i=0;i<len1;i++)
{
map.put(a[i], 1);
}

for(int i=0;i<len2;i++)
{
if(map.containsKey(b[i]))
{
int val=map.get(b[i]) +1;
map.put(b[i], val);
}

if(!map.containsKey(b[i]))
{
flag=1;
System.out.println("Missing number is :- " + b[i]);
}
}
}

else
{
for(int i=0;i<len2;i++)
{
map.put(b[i], 1);
}

for(int i=0;i<len1;i++)
{
if(map.containsKey(a[i]))
{
int val=map.get(a[i]) +1;
map.put(a[i], val);
}

if(!map.containsKey(a[i]))
{
System.out.println("Missing number is :- " + a[i]);
}
}
}

}

}

import java.util.HashMap;


public class FindMissingandDuplicate {
	
	static int  flag=0;

	public static void main(String[] args) {
		
		int a[]={1,3,5,6,8};
		int b[]={1,5,6,8};
		
		FindMissingandDuplicate obj=new FindMissingandDuplicate();
		obj.findMissing(a,b);
		
		if(flag==0)
			System.out.println("No missing number");
		// TODO Auto-generated method stub

	}

	private static void findMissing(int[] a, int[] b) {
		// TODO Auto-generated method stub
		int len1=a.length;
		int len2=b.length;
		
		HashMap <Integer,Integer> map=new HashMap<Integer,Integer>();
		
		if(len1<len2)
		{
			for(int i=0;i<len1;i++)
			{				
				map.put(a[i], 1);
			}
			
			for(int i=0;i<len2;i++)
			{	
				if(map.containsKey(b[i]))
				{
					int val=map.get(b[i]) +1;
					map.put(b[i], val);
				}
				
				if(!map.containsKey(b[i]))
				{
					flag=1;
					System.out.println("Missing number is :- " + b[i]);
				}
			}
		}
		
		else
		{
			for(int i=0;i<len2;i++)
			{				
				map.put(b[i], 1);
			}
			
			for(int i=0;i<len1;i++)
			{	
				if(map.containsKey(a[i]))
				{
					int val=map.get(a[i]) +1;
					map.put(a[i], val);
				}
				
				if(!map.containsKey(a[i]))
				{
					System.out.println("Missing number is :- " + a[i]);
				}
			}
		}
		
	}

}

import java.util.HashMap;


public class FindMissingandDuplicate {

static int flag=0;

public static void main(String[] args) {

int a[]={1,3,5,6,8};
int b[]={1,5,6,8};

FindMissingandDuplicate obj=new FindMissingandDuplicate();
obj.findMissing(a,b);

if(flag==0)
System.out.println("No missing number");
// TODO Auto-generated method stub

}

private static void findMissing(int[] a, int[] b) {
// TODO Auto-generated method stub
int len1=a.length;
int len2=b.length;

HashMap <Integer,Integer> map=new HashMap<Integer,Integer>();

if(len1<len2)
{
for(int i=0;i<len1;i++)
{
map.put(a[i], 1);
}

for(int i=0;i<len2;i++)
{
if(map.containsKey(b[i]))
{
int val=map.get(b[i]) +1;
map.put(b[i], val);
}

if(!map.containsKey(b[i]))
{
flag=1;
System.out.println("Missing number is :- " + b[i]);
}}}

else
{
for(int i=0;i<len2;i++)
{
map.put(b[i], 1);
}

for(int i=0;i<len1;i++)
{
if(map.containsKey(a[i]))
{
int val=map.get(a[i]) +1;
map.put(a[i], val);
}

if(!map.containsKey(a[i]))
{
System.out.println("Missing number is :- " + a[i]);
}}}}}

import java.util.HashMap;


public class FindMissingandDuplicate {

static int flag=0;

public static void main(String[] args) {

int a[]={1,3,5,6,8};
int b[]={1,5,6,8};

findMissing(a,b);

if(flag==0)
System.out.println("No missing number");
// TODO Auto-generated method stub

}

private static void findMissing(int[] a, int[] b) {
// TODO Auto-generated method stub
int len1=a.length;
int len2=b.length;

HashMap <Integer,Integer> map=new HashMap<Integer,Integer>();

if(len1<len2)
{for(int i=0;i<len1;i++){map.put(a[i], 1);}
for(int i=0;i<len2;i++)
{if(map.containsKey(b[i]))
{ int val=map.get(b[i]) +1;
map.put(b[i], val);
}if(!map.containsKey(b[i]))
{ flag=1;
System.out.println("Missing number is :- " + b[i]); }}}
else{for(int i=0;i<len2;i++){map.put(b[i], 1);}
for(int i=0;i<len1;i++)
{if(map.containsKey(a[i])){
int val=map.get(a[i]) +1;
map.put(a[i], val);}
if(!map.containsKey(a[i]))
{System.out.println("Missing number is :- " + a[i]);}}}}}

If the question is only about one element missing in one of the array then
probably just add two arrays to s1, s2. Let us say l1, l2 is length of both arrays respectively. Now if l1>l2 then s1-s2 gives exact element.

2 methods: add all elements from array1 and array2 separately, then subset act the sums. Second method: XOR all elements array1 and array2 separately, then XOR them together

Quick Solution

private static int FindMissingElement(int[] arr1, int[] arr2)
        {
            int sum1 = arr1.Sum();
            int sum2 = arr2.Sum();

            return (sum1 > sum2 ? sum1 - sum2 : sum2 - sum1);
            //return Math.Abs(sum1 - sum2);
        }

#include <stdio.h>
int a[]={1,3,5,6,8};
int b[]={1,5,6,8};

int main()
{
	int i,j;
	for(i=0;a[i]!=0x00;i++)
	{
		int missing =1;
		for(j=0;b[j]!=0x00;j++)
		{
			if(a[i]==b[j])
				missing=0;
		}
		if(missing == 1)
			printf("%d",a[i]);
	}
	return 0;
}

package Test;

import java.util.HashSet;
import java.util.Set;

public class ABCD {

	public static void main(String[] args) {
		int a[]={1,2,3,4,5,6,7};
		int b[]={1,3,4,5,6,7};
		Set<Integer> set1=new HashSet<Integer>();
		Set<Integer> set2=new HashSet<Integer>();
		for(int num:a)
			set1.add(num);
		
		for(int num:b)
			set2.add(num);
		
		set1.removeAll(set2);
		System.out.println(set1);
			
		

	}

}

#include<stdio.h>
int main()
{
int arr[]={1,2,3,4,5,6};
int arr1[]={1,3,4,5,6};
int i=0;
int j=0;
int k=1;
int ans=0;
for(i=0;i<6;i++)
{
if(k==0)
{
printf("%d\n",ans );
break;
}
for(j=0;j<5;j++)
{
if(arr[i]==arr1[j])
{
k=1;
break;
}
else
{
ans=arr[i];
k=0;
}
}
}
}

It seems that no one has thought of the solution using bitwise tricks. :-) I like the solution with sums, but it has the obvious problem that it can overflow; sure, we could mitigate that with clever interleaving, but that complicates the solution.

First recall that n XOR n = 0 for any integer n. More generally, if we XOR an integer with itself an even number of times, we'll always get zero.

Now the two arrays contain exactly the same elements with exactly the same multiplicity, except for the missing element. Thus all elements---except the missing one---have even multiplicity. It follows that if we XOR all the elements---from both arrays---they all cancel out, except the element with odd multiplicity, which is the element we're looking for.

In C++, you could do this as follows.

int find_missing(const std::vector<int>& a, const std::vector<int>& b) {
    int missing = 0;
    for (const auto& num : a) missing ^= num;
    for (const auto& num : b) missing ^= num;
    return missing;
}

C# code:

//Time Complexity: O(n)
        public static int Findmissing(int[] A1, int[] A2)
        {

            Dictionary<int, int> D = new Dictionary<int, int>();

            for (int i = 0; i < A1.Length; i++)
            {
                if (D.ContainsKey(A1[i]))
                    D[A1[i]]++;
                else
                    D[A1[i]] = 1;
            }

            for (int i = 0; i < A2.Length; i++)
            {
                if (D.ContainsKey(A2[i]))
                    D[A2[i]]++;
                else
                    D[A2[i]] = 1;
            }

            int missing=0;
            foreach (KeyValuePair<int, int> pair in D)
            {
                if (pair.Value == 1)
                {
                    missing = pair.Key; // Found
                    break;
                }
            }

            return missing;
        }

For a duplicate array:

public static int Findmissing2(int[] A1, int[] A2)
        {

            for (int i = 0; i < A2.Length; i++)            //Since second array is a copy
            {
                if (A1[i] != A2[i])
                    return A1[i];
            }

            return A1[A1.Length-1];
        }

import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

public class ArrayUtil {
	private static void checkPreConditions(int arr1[], int arr2[]) {
		if (Objects.isNull(arr1) || Objects.isNull(arr2)) {
			throw new NullPointerException("Arrays Shouldn't be null");
		}

		if (arr1.length != arr2.length + 1) {
			throw new IllegalArgumentException("Illegal Arguments");
		}
	}

	public static int approach1(int arr1[], int arr2[]) {
		checkPreConditions(arr1, arr2);

		int data = arr1[0];

		for (int i = 1; i < arr1.length; i++) {
			data ^= arr1[i];
			data ^= arr2[i - 1];
		}

		return data;
	}

	public static int approach2(int arr1[], int arr2[]) {
		checkPreConditions(arr1, arr2);

		int sum1 = arr1[0], sum2 = 0;

		for (int i = 1; i < arr1.length; i++) {
			sum1 = sum1 + arr1[i];
			sum2 = sum2 + arr2[i - 1];
		}

		return sum1 - sum2;
	}

	public static int approach3(int arr1[], int arr2[]) {

		checkPreConditions(arr1, arr2);

		Set<Integer> hashSet = new HashSet<>();

		for (int i : arr1) {
			hashSet.add(i);
		}

		for (int i : arr2) {
			if (hashSet.contains(i))
				hashSet.remove(i);
		}

		for (int missed : hashSet)
			return missed;

		return -1;
	}
}

In Python, we can use set() to get answers.
a = [1,2,3,4,5,6,7]
b = [1,3,4,5,6,7]

print set(a) - set(b)

package com.my.algo.problemsolving;

public class MissingElement {

	public static void main(String[] args) {
		int[] a1 = {1,2,3,4,5,6,7};
		int[] a2 = {1,2,4,5,6,7};
		int sum1 = 0; int sum2 = 0;
		if (a1.length == a2.length) {
			System.out.println("Both arrays are identical.. not missing");
			System.exit(0);
		}
		for (int i = 0; i < a1.length; i++) {
			sum1 += a1[i];
		}

		for (int i = 0; i < a2.length; i++) {
			sum2 += a2[i];
		}
		if (a1.length > a2.length)
			System.out.println("Missing element : " + (sum1 - sum2));
		else
			System.out.println("Missing element : " + (sum2 - sum1));
			
		
}

}

binary search is actually a good solution
check the mid number is the array, say we find 5. If it should be 4, then we know that the missing number is on the left. If it's should exactly 5, then the missing number is on the right.

public class MissingElement {

public static void main(String args[]) {
int[] arr1 = { 1, 2, 3, 4, 6, 7, 8, 9 };
int[] arr2 = { 1, 2, 3, 6 };

System.out.println("The missing elements are: ");
for (int i = 0; i < arr1.length; i++) {
if (MissingElement(arr1[i], arr2)) {
} else {
System.out.println(arr1[i]);
}
}
}

private static boolean MissingElement(int arr1, int[] arr2) {
for (int i = 0; i < arr2.length; i++) {
if (arr2[i] == arr1) {
return true;
}
}
return false;
}
}

public void missingElement(Integer[] a, Integer[] b){
       List<Integer> ls =   Arrays.asList(a);
       List<Integer> ls1 =   Arrays.asList(b);
        Set<Integer> set1 = new HashSet<Integer>(ls);
        set1.removeAll(ls1);
        Iterator<Integer> iths = set1.iterator();
        while(iths.hasNext()){
            System.out.println(iths.next());
        }
    }

Python solution

for i in array1:
if i not in array2:
print i

I could think of 3 options below:
1) The one user Tal suggested at first --> sum of Array1 - Sum of Array2
2) Using linear search to go through each element of both the arrays and find what's missing
3) Another linear approach, but this time convert the arrays to ArrayList and use contains function to find whether the element is exist or not

2

Use Binary Search O(log n) time complexity and O(1) auxiliary space complexity.