Java program to find missing number in an array

Sponsored Links

Ad by Google

I just faced an interview where first round was technical written exam based on some logical question belongs to String, Array and Puzzle. One of the question was something like "We have a container having 100 balls each ball marked with a positive natural number from 1 to 100 for example 1,2,3,4,5.....100. Each ball marked with exactly only and only once number. So total 100 balls marked with 100 numbers". Now one ball is randomly picked out from the container. Find the ball picked one with which number.
Note: Try to find the missing one with quickest way.

Lets try to solve this. Ok this can be doable with O(n). We have to iterate the natural numbers and compute the sum of natural numbers for example numbers to be calculated are from 1 to N. From the above problem statement N is 100 and the sum of N numbers can be expressed with Nx(N+1)/2 so sum will be 100X(100+1)/2 = 5050 and subtract the sum of array from 5050.

Ok got it now lets implement this in java programing, assuming numbers here 10 instead of 100.

Number.java

package com.sample.program;

public class Number {

 public static int returnMissingNum(int[] numbers) {
  int missingNumber = 0;
  int sumOfN = 0;
  int missingIdx = -1;
  for (int i = 0; i < numbers.length; i++) {
   if (numbers[i] == 0) {
    missingIdx = i; // missing number index.
   } else {
    sumOfN += numbers[i];
   }
  }
  int total = numbers.length * (numbers.length + 1) / 2; // n*(n+1)/2
  missingNumber = (total - sumOfN);
  System.out.println("Missing number is =" + missingNumber + " at index = "
    + missingIdx);
  
  return missingNumber;
 }

 public static void main(String[] args) {
  
  // missing number is represented by 0
  int[] numbers = { 5, 2, 3, 4, 1, 6, 0, 8, 9, 10 }; 
  returnMissingNum(numbers);
 }
}

OUT PUT:
Missing number is =7 at index = 6

Sponsored Links