0

How to find missing number?

Given: two arrays as input, and find a number that is present in first array but is missing in second array.

public class Array2 
 {
public void missingnos(int a[],int b[])
{
    for(int i=0;i<a.length;i++)
    {
        for(int j=i+1;j<a.length;j++)
        {
            if(a[i]>a[j])
            {
                int c=a[i];
                a[i]=a[j];
                a[j]=c;
            }
        }
        System.out.print(a[i]);
    }
    for(int i=0;i<b.length;i++)
    {
        for(int j=i+1;j<b.length;j++)
        {
            if(b[i]>b[j])
            {
                int c=b[i];
                b[i]=b[j];
                b[j]=c;
            }
        }
        System.out.print(b[i]);
    }
    int d[]=new int[a.length];
    d=b;
    int missing=0;
    for(int i=0;i<b.length;i++)
    {
        if(a[i]!=d[i])
        {
            missing=a[i];
            break;
        }
    }
    System.out.println();
    System.out.print(missing);
}
public static void main(String[] args) {
    Array2 a2= new  Array2();
    int a[]={1,4,3,5,6};
    int b[]={4,1,5,3};
    a2.missingnos(a,b);

}

}

Test Case: when I remove 6 & 3 from array "a" and "b" respectively I get answer as 3 which is correct, but when i don't remove i get answer as 0.

Why is it so?

Improve this question
1
  • Just a suggestion. You don't need to use the for loops twice to initialize values to an array. You can do that in the same for loops. Using multiple for loops increases the complexity of a program. Nothing to worry about now, but in the long run, these things are important to write an effective program. Commented Mar 16, 2014 at 7:49

11 Answers 11

Reset to default
6

Here's a way to solve this problem in O(1) auxiliary space and O(n) time. The solution is subject to the below constraints:
1) arr2 has only one element missing from arr1.
2) arr2.length=arr1.length-1 OR arr2 has the missing element replaced by 0.

Solution: Simply take xor of all the elements of the two arrays. The resulting integer is the answer

Code: 

public static void findMissing(){
    // TODO Auto-generated method stub
    int[] arr1={3,7,2,90,34};
    int[] arr2={2,7,34,3};  
    int xor=0;
    for(int i=0;i<arr1.length;i++){
        xor^=arr1[i];
    }
    for(int i=0;i<arr2.length;i++){
        xor^=arr2[i];
    }
    System.out.println("missing number: "+xor);
}

Why it works? Say arr1={1,2,3,4} and arr2={1,2,4}. Taking xor of all element =>
1^2^3^4^1^2^4
= (1^1)^(2^2)^(4^4)^3
= 0^0^0^3
=3

Another solution as proposed by RP- is also very good and solves this problem in the same space and time complexities, but there is a chance of an overflow while calculating sums.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

your solution is nice but works for just 1 missing number
yes that's right, since that's what the problem statement says. I can't think of a solution which works in O(1) space and O(n) time and provides multiple missing numbers(If someone can provide that, that would be great!). Ofcourse if you want to find multiple missing numbers, there is a way to do it in O(n) space and O(n) time if you put all the numbers of arr2 in a HashSet and iterate over arr1 to find the missing numbers.
I don't want to use APIs :)
Then you can't find multiple missing numbers in O(n) time in an unsorted array. You can do O(nlgn) at best :)
1

Your main problem is that you're trying to do it in a too complex way, and to do everything inside a single method. Sorting the arrays is not necessary, and doing it as you're doing is very inefficient, and doesn't use the Arrays.sort() method that would do it for you.

Try to split the problem into simple tasks:

  1. Find if a number is present in an array. That should be a method (boolean isPresent(int number, int[] array)).
  2. Iterate through the first array, and for each element, find if it's present in the second one. That should be your main method, using the first one:

.

public class Arrays2 {
    public static void main(String[] args) {
        int[] a = {1, 4, 3, 5, 6};
        int[] b = {4, 1, 5, 3};
        findMissingNumber(a, b);
    }

    private static void findMissingNumber(int[] a, int[] b) {
        for (int n : a) {
            if (!isPresent(n, b)) {
                System.out.println("missing number: " + n);
                break;
            }
        }
    }

    private static boolean isPresent(int n, int[] b) {
        for (int i : b) {
            if (n == i) {
                return true;
            }
        }
        return false;
    }
}
Improve this answer

6 Comments

Actually I am doing it in a simple manner. I m not using APIs in it. This type of questions with certain conditions are asked in interviews.
OK, I'll provide my full answer, which will be correct, and we'll see if mine is simpler than yours (which doesn't work). Decomposing a task in simple tasks is an essential part of any design. And having simple methods with a single responsibility is a key part of maintainability. Try my code with any kind of array, including arrays containing duplicate values. Try yours with the same and see the difference.
You used two methods here. But sometimes interviewers ask to "write 'a' method for a particular program or for a particular output". Does it mean we can write more than one method?
Methods should do a single thing, and thus have a single responsibility. 5 or 6 lines of code in a method is much better that 100. An interviewer (unless he's a really, really bad one) will like it if you split a complex problem into simple problems using several methods. If he doesn't like it, the you'd better work sowewhere eles, where you'll learn good coding practices.
@svz: 4 is present in the first array, and is also present in the second one. That what is being asked.
|
1

When you have different sized arrays, then you need to stop as soon as one array reaches to its max position. Here you are getting answer as 0 because the b array has only 4 elements.

The correct code is:

int d[]=new int[a.length];
    d=b;
    int missing=0;
    for(int i=0;i<a.length;i++)
    {
        if(i>=b.length || a[i]!=d[i])
        {
            missing=a[i];
            break;
        }
    }
    System.out.println();
    System.out.print(missing);
Improve this answer

Comments

1

Think about this as a problem of efficient algorithm. Using nested loops on arrays will give you a O(n^2) time complexity which is not desired.

However if you use something like a HashSet your time complexity will be O(m+n) where m being the length of first array and n being the length of second array.

Something like below

import java.util.ArrayList;
import java.util.HashSet;

public class MissingNumbers {

    public static Integer[] missingNumbers(Integer[] firstArray,Integer[] secondArray) {
        ArrayList<Integer> alDups = new ArrayList<Integer>();
        int dupCount = 0;
        HashSet<Integer> setOfSecondArr = new HashSet<Integer>();
        // Add second array into hash set of integers
        for (int i : secondArray) {
            setOfSecondArr.add(i);
        }
        // Now add the first array, if it gets successfully added to the set
        // it means second array did not have the number
        for (int i : firstArray) {
            if (setOfSecondArr.add(i)) {
                alDups.add(i);
                dupCount++;
            }
        }

        return alDups.toArray(new Integer[dupCount]);
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        for (int i : missingNumbers(new Integer[] { 1, 2, 3, 5, 6 },
                new Integer[] { 1, 2, 4 })) {
            System.out.println(i);
        }
    }

}
Improve this answer

Comments

1

I know this is an old question, but might help somebody. We don't really need to compare each and every element form first and second array..

Just take the sums (in long to avoid the overflow) from each array and subtract one array's sum with other array's sum. And the result is the missing number.

Improve this answer

2 Comments

Sorry this is too late. Your answer finds the missing nos if it is 1, But what if we have more than one missing numbers?
Yes, that's the limitation with this approach, but in general in interviews people expect you to think differently rather than a bootstrap approach and they care weather you care about the given example and derive something out of very quickly.
0 
for(int i=0;i<b.length;i++)
{
    if(a[i]!=d[i])
    {
        missing=a[i];
        break;
    }
}

should be changed to
for(int i=0;i<min(a.Length,b.length);i++) because you are not handling case when size of both arrays are not same .

Also

int d[]=new int[a.length]; d=b;

what if length(b)>length(a) ?
You have many errors , first try to work it on pen and paper , then transform into code .

Improve this answer

2 Comments

To add to that d[] has be declared to take the length of a, but assigned the reference to b[]. int d[]=new int[a.length]; d=b; This will also be a problem if the array lengths are not same
According to my question my first arrary's length should be more than second array. So I wrote this code.
0

you have complicated your logic. why use a 2nd combination of for loops when you could have done the comparison in the first for loop itself. you just need to display the numbers from the 1st array that are not present in 2nd array right

Improve this answer

Comments

0 
public class FindMissingNumbers {


    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int i,j,size1,size2;
        boolean flag=false;
        Scanner sc = new Scanner(System.in);

        System.out.println("Enter 1st array lenght");
        size1=sc.nextInt();//input array size
        int[] a=new int[size1];

        System.out.println("Enter "+size1+" Values of 1st array");
        for(i=0;i<size1;i++){
            a[i]=sc.nextInt();//read first array list
        }


        System.out.println("Enter 2st array lenght");
        size2=sc.nextInt();//input array size
        int b[]=new int[size2];
        System.out.println("Enter Values of 2st array");
        for(i=0;i<size2;i++){
            b[i]=sc.nextInt();//read second array list
        }


        System.out.println("Numbers which are not present in 1nd array");
        for(i=0;i<size2;i++)
        {
            flag=false;
            for(j=0;j<size1;j++)
            {
                if(a[j]==b[i]) 
                {
                    break;
                }
                else if(a[j]!=b[j] && j==size1-1){
                    flag=true;
                }
            }
            if(flag==true){
                System.out.println(b[i]);
                flag=false;
            }

        }

    }

}
Improve this answer

Comments

0 
 Diff([1,2,3,4] [1,2,3]) = [4] 
 Diff([1,2,2,2], [1,2]) = [2,2] 
 Diff([2, 2, 1, 2], [1,2]) = [2,2]
 Diff([1,1,1,1,1,1,2,2,2,2,2,2], [1,1,2,2]) = [1,1,1,1,2,2,2,2]

public static void main(String[] args) {
        int[] a = {1,2,3,4};
        int[] b = {1,2,3};

        Arrays.sort(a);// The sorting only required for input example 3.
        Arrays.sort(b);//

        List<Integer> listA = new ArrayList<>();

        for( int i = 0; i < a.length; i++ ) {
            if( i >= b.length  ) { 
                listA.add(a[i]);
            }

            for( int j = i; j < b.length; j++ ) {
                if( a[i] == b[j] || listA.contains(a[i])) {
                    break;
                } else {
                    listA.add(a[i]);
                }
            }
        }//end of for loop
        System.out.println(listA);

    }

With is algorithem, only example 4 won't work.
Improve this answer

Comments

0

sum(first array elements) - sum(second array elements) Time complexity : o(n)+o(n-1)

Improve this answer

Comments

-1

Try this:

static void Main(string[] args)
    {
        int[] a = {1, 4, 3, 5, 6};
        int[] b = {4, 1, 5, 3};
        for (int i = 0; i < a.Length; i++)
        {
            if(!b.Contains(a[i]))
            {
                Console.WriteLine("missing number: " +a[i]);
            }
        }

        Console.ReadKey();
    }
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.