Tuesday, April 26, 2011

Tricky Java question: finding the missing number

So here is the detailed question:
Question (1): Suppose a number is missing in a jumbled sequence of 1 to 100. So, find the missing number. So the series may look like this:
{2,4,1,100,67.....}

Solution: Sum of natural numbers is = n*(n+1)/2. So we will find the sum of the series we have and subtract it from the sum of natural numbers from 1 .. 100 and that's how we got the missing number. To illustrate the logic we will take a list of only 10 numbers.
public class FindOneMissingNumber {
public static void main(String[] args) {
// in the below jumbles series of 1-10, 7 is missing
int [] arr = {9,4,5,1,10,2,6,3,8};

// Sum of numbers till 10
int sumNaturalNumbers = 10 *(10+1)/2;
int sumOurSeries=0;
for(int i=0;i<arr.length;i++){
sumOurSeries +=arr[i];
}
System.out.println("Sum of our series: "+sumOurSeries);
System.out.println("missing number= "+(sumNaturalNumbers-sumOurSeries));
}
}


Now let us make the situation more complicated. Suppose we do not know how many numbers are missing in the series it can be 2, 3, 4 or just any number of digits missing. How to figure out which digits are missing.

Here is the solution, see if you can figure out apart from these:
Solution (1)
Approach:
  1. Create a new array b[] of the size of missing numbers array a[] +number of digits missing
  2. copy the numbers from first array into second array so that b[a[i-1]] = a[i]
  3. Now search the second array to see which field is contains zero
  4. Missing fields = array positions having zero + 1

Code listing:
/**
*
* @author Dharmvir Singh
* Solution has the complexity as O(n)
*/
public class FindOneMissingNum {
public static void main(String[] args) {
// two numbers are missing: 2, 6, 10
int a [] = {3,5,7,1,4,8,9};
int countOfMissingDigits=3;
int b [] = new int [a.length+countOfMissingDigits];
for (int i = 0; i < a.length; i++) {
b[(a[i]-1)]=a[i];
}
for (int i = 0; i < b.length; i++) {
if(b[i]==0){
System.out.println("missing number is"+(i+1));
}
}
}

}

SO the question in the comments can be solved either by the solution given above or there is one more solution. This solution also has the complexity O(n).
So here is the solution:
Approach:
  1. Suppose series is a[]={4,2,3,1,2}. Suppose positions here are starting from i= o to 4
  2. Start marking the numbers at positions a[a[i]-1] as negative.
  3. In above process exclude all the numbers which are already marked negative(-)
  4. All the positions will have their numbers marked (-) except the positions representing the missing number
Code listing:
public class FindMissingNum {

 /**
  * @param args
  */
 public static void main(String[] args) {

  // two numbers are missing: 2, 6
  int a[] = { 3, 5, 1, 7, 1, 3, 4, 8, 7, 9 };
  int t1, t;
  for (int i = 0; i < a.length; i++) {
   t = a[i];
   // if t is already negative then make it positive as
   // positions cannot be negative
   if (t < 0) {
    t1 = -t;
    if (a[t1 - 1] > 0)
     a[t1 - 1] = -a[t1 - 1];
   } else {
    if (a[t - 1] > 0)
     a[t - 1] = -a[t - 1];
   }

  }
  // Print the missing numbers
  for (int i = 0; i < a.length; i++) {
   if (a[i] > 0) {
    System.out.println("Missing Number:" + (i + 1));
   }
  }
 }
}

Related posts on this blog:
Checking if i=4or5or6 without using any logical operator like && or ||

6 comments:

  1. Hey what about if suppose the array has a number repeated on the position of missing number as shown:

    4,1,2,3,4,5,8,9,10,1

    The above series has two numbers missing any other solution apart from the one shown here?

    ReplyDelete
  2. "You can find out the missing number in array by following algorithm:

    /* getMissingNumber takes array and size of array as arguments*/
    int getMissingNumber (int arr[], int num)
    {
    int i;
    /* For xor of all the elemets in arary */
    int x1 = a[0];
    /* For xor of all the elemets from 1 to n+1 */
    int x2 = 1;

    for (i = 1; i< n; i++)
    x1 = x1^a[i];

    for ( i = 2; i <= n+1; i++)
    x2 = x2^i;

    return (x1^x2);
    }

    I also found some more possible solutions. you can check out below link for more solutions:

    Find out missing number in an array in java"









    ReplyDelete
  3. http://newtechnobuzzz.blogspot.in/2014/07/find-out-missing-number-in-array-in-java.html

    ReplyDelete
  4. You can find out the cycle or loop in a single linked list by using two pointer approach.
    Below link can be useful to find out the algorithm to find cycle or loop in linked list

    Find out loop or cycle in linked list in java

    http://newtechnobuzzz.blogspot.in/2014/07/how-to-find-loops-or-cycles-in-linked.html

    ReplyDelete
  5. I have read your blog its very attractive and impressive. I like it your blog.

    Java Training in Chennai Core Java Training in Chennai Core Java Training in Chennai

    Java Online Training Java Online Training Core Java 8 Training in Chennai Core java 8 online training JavaEE Training in Chennai Java EE Training in Chennai

    ReplyDelete