2

Is it possible to find out one missing element from one array that is not present in other array using single for loop in Java

e.g. a1 = {2,5,1,9,3,4} , length n+1

     a2 = {2,4,1,5,3}   , length n

missing element - 9 Using only a single for loop not by collections. Is it possible??

siso
  • 265
  • 1
  • 7
  • 20
  • 2
    Sounds like an interview question. A few clarifications: Do you know the max/min values in the array beforehand? Are you only truly allowed only one for loop or the result just has to be O(n)? – Mshnik Aug 10 '14 at 07:55
  • yes its a interview question, max/min values are not given beforehand. The interviewer told me to solve using only one for loop, not even allowed to sort the array :( – siso Aug 10 '14 at 08:02
  • 2
    If you KNOW that there is just one element in a1 that not in a2 then you can solve with simple math (subtract and delete) – odedsh Aug 10 '14 at 08:03

3 Answers3

9

At the most basic, if we are always talking about numbers, just sum the suckers.

int sumOne = 0;
int sumTwo = 0;

for(int i = 0; i < a1.length; i++){
    sumOne += a1[i];
    if(i < a2.length)
        sumTwo += a2[i];
}

int missingNumber = sumOne - sumTwo;

If the elements aren't always numbers... Ask for more loops.

Mshnik
  • 7,032
  • 1
  • 25
  • 38
  • 2
    Just as an aside, it's worth noting that this will ***ONLY*** work for one missing number. If there is more than one missing number it will fail. – christopher Aug 10 '14 at 08:07
  • That's true. If you want more than that, you apparently can do it with some insane math: http://stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-numbe?rq=1 – Mshnik Aug 10 '14 at 08:54
  • Why only integers? This solution can find any rational number IMO. – Abhishek Bansal Aug 10 '14 at 09:40
4

Find missing element using XOR

class Main {
    public static void main(String[] args) {
        int[] a1 = { 2, 5, 1, 9, 3, 4 };
        int[] a2 = { 2, 4, 1, 5, 3 };

        int missingElement = a1[a1.length - 1];
        for (int i = 0; i < a2.length; i++) {
            missingElement = missingElement ^ a1[i] ^ a2[i];
        }

        System.out.println(missingElement);
    }
}
sujithvm
  • 2,351
  • 3
  • 15
  • 16
  • Though overflow will correct itself via modular arithmetic with the summing solution, I find this solution to be more elegant. – Apriori Aug 10 '14 at 20:41
2

sum the 2 arrays in one loop then subtract (max - min) = the missing element

  • This has already been answered, better. Please either think of a different solution or remove your answer. – christopher Aug 10 '14 at 08:07
  • 1
    when i was writing it, some one else wrote ! –  Aug 10 '14 at 08:09
  • That's fair enough! But we don't really like duplicate answers here. I guess now someone has upvoted it, there's no chance of you deleting it. Screw it. Have a +1. – christopher Aug 10 '14 at 08:11