Crea sito

Find the missing number in two Arrays

PROBLEM:

Let A,B be two Arrays. Suppose B is a sub-array of A and there is one element that appears only in A.

Find the element of A that is missing in B.

Example:

A = 1, 5, 6, 3, 4, 2

B = 6, 3, 5, 1, 4

Output: 2

IDEA:

If you want to try by yourself this problem, stop reading this post and open your IDE.

It is a good exercise to try it, then return back to this page and read my solution. In this way you could approach some different design techniques.

The idea for the solution of this algorithmic challenge is to check, for every element of A, if an equal number is inside the Array B. So you choose the first number of A, then iterate trough all numbers of B and if the element is not present (thus A[x] = B[x] never happen) then the algorithm must return A[x].

SOLUTION:

public int findMissingNumber(int[] A, int[] B) {
		
		
		
		for(int i = 0; i < A.length; i++) {
			
			boolean present = false;
			
			for(int j = 0; j < B.length; j++) {
				if(A[i] == B[j])
					present = true;
			}
			
			if(present == false) {
				return A[i];
			}
			
			
		}
		
		return A[0];
	}

CONCLUSION:

The worst case running time of this Algorithm is O(n^2), because of the nested loops.

I hope you have found this post useful and remember that for any idea, suggestion or question you can post a comment below this page.

See you 🙂