CODEWITHSUNDEEP
java
Newinjava
Newinjava

Reputation: 960

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

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?

Upvotes: 0

Views: 22760

Answers (11)

Rajakumar Munna
Rajakumar Munna

Reputation: 99

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

Upvotes: 0

ashish singh
ashish singh

Reputation: 7

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();
    }

Upvotes: -1

Yoga Gowda
Yoga Gowda

Reputation: 367

 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.

Upvotes: 0

Nitin Sindhe
Nitin Sindhe

Reputation: 71

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;
            }

        }

    }

}

Upvotes: 0

yetAnotherCoder
yetAnotherCoder

Reputation: 141

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.

Upvotes: 6

RP-
RP-

Reputation: 5837

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.

Upvotes: 1

Puru--
Puru--

Reputation: 1121

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);
        }
    }

}

Upvotes: 1

vikeng21
vikeng21

Reputation: 531

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

Upvotes: 0

JB Nizet
JB Nizet

Reputation: 692281

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;
    }
}

Upvotes: 1

Vinod Satpute
Vinod Satpute

Reputation: 51

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);

Upvotes: 1

Aseem Goyal
Aseem Goyal

Reputation: 2723

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 .

Upvotes: 0

Related Questions