Question
This time I want to concider an exercise which Amazon gave on interviews several years ago. I have no proof links on this information, so let’s imagine that previous sentence is truth. Are you ready for the logical task? Let’s start.

You must find a missing number in an array. The array consists of numbers from 1 to 10 in random sequence. But this is not all… One of the numbers in the array is absent and you must find it. So, you can start solving the problem… But, no! Wait a minute. There is one more important constraint – you can use not more then one loop. Good luck =)

Here are some examples:

  • 5,6,9,4,1,2,8,3,10 – the result will be: 7
  • 2,10,4,5,6,7,8,9,3 – the result will be: 1
  • 1,3,2,6,5,7,8,10,9 – the result will be: 4

Here is my solution:

...
	public static void main(String[] args) {
		
		int[] arr = {10,9,3,6,4,7,8,1,2};
		int length = arr.length;
		
		int indexes = 10;
		int values = 0;
		
		for (int i = 0; i < length; i++) {
			indexes += i+1;
			values += arr[i];
		}
		
		int result = indexes - values;
		
		System.out.println("Missing number is: "+result);
	}
...

Try to solve this exercise by yourself. It will be great to see more efficient solution in the comments.
Don't forget to like my blog on FaceBook.

About The Author

Mathematician, programmer, wrestler, last action hero... Java / Scala architect, trainer, entrepreneur, author of this blog

  • Ameise

    My solution approach for example above, first use quick sort for sorting array and then just compare one item with another.

    • Fruzenshtein

      This mean that you will use more then one loop, but you can use just one =)

  • There is a simplification for your solution. There is no need to sum the indexes. It is a arithmetic progression. S= (a1 + an)*n/2 where a1 = 1, an, n = array length. Also I assume that a bitwise operation-based improvement exists.

    • Fruzenshtein

      Bingo!

  • vkopchenin

    int[] array = {1,3,2,6,5,7,8,10,9};

    // sum of arithmetic progression
    int sum_all = ((1 + 10) * 10) / 2;

    int sum_part = 0;
    for(int i: array) {
    sum_part += i;
    }

    System.out.println(“Result:” + (sum_all – sum_part));

  • Rahul Sahu

    public static void main(String[] args) {
    int [] array_int = {2,5,3,7,1,6,8,10,4};
    Arrays.sort(array_int);
    int i=1;
    for (;i<=10;i++) {
    if(i==array_int[i-1])
    continue;
    else
    break;
    }
    System.out.println(i);
    }

  • jitendra varshney

    simple way there is no duplicate and finding the one missing numbner in series from start 1

    int arr[]={1,2,3,4,5,6,7,9,10};

    for(int i=0;i<arr.length;)

    {

    if(arr[i]!=i+1)

    {

    System.out.println((i+1));

    break;

    }

    else

    {

    i++;

    }

    }

  • Igor Lantushenko

    Hey, how about little improves ?:)

    public static void main(String[] args) {

    int[] arr = {10,9,3,6,4,7,8,1,2};
    int length = arr.length;
    int result = arr.length + 1;

    for (int i = 0; i < length; i++) {
    result += i + 1 – arr[i];
    }

    System.out.println("Missing number is: "+result);
    }

  • A good post. To be honest, I was rehearsing within myself of the logic and it did exactly match with yours. I had few other ideas but finally concluded with the summation and there yours!

Close