Sunday, 31 January 2016

Find all missing numbers in a sequence......

Problem:- Given a list of numbers from 1 to N where more than one numbers are                    missing between 1 to N find all of them .

here is the code ......


       
public class AllMissingNumbersProblem {
 static int missNum;
 static int largestNum;
 static boolean[] keepTrack;
 public static void main(String args[]) {

  int[] arr = {
   4,
   2,
   6,
   5,
   3,
   1,
   8,
   12,
   9,
   11
  };
  largestNum = findLargestNumber(arr);
  keepTrack = new boolean[largestNum + 1];

  for (int i = 0; i < arr.length; i++)
   keepTrack[arr[i]] = true;

  System.out.println("Missing numbers are listed below....");
  for (int p = 1; p < keepTrack.length; p++) {
   if (!keepTrack[p])
    System.out.println(p);
  }

 }
 public static int findLargestNumber(int[] arr) {
  int temp;
  for (int i = 0; i < arr.length - 1; i++) {
   if (arr[i] > arr[i + 1]) {
    temp = arr[i + 1];
    arr[i + 1] = arr[i];
    arr[i] = temp;
   }
  }
  return arr[arr.length - 1];
 }
}

       
 

Find the missing number......

Problem:- Given a list of number from 1 to N find the missing number ....

Logic -Just calculate sum of N natural numbers (n*(n+1))/2.
            Then subtract the sum of all given numbers from above calculated sum                    and you will get missing number.

here is the code......


       

public class MissingNumberProblem {
 static int missNum;
 static int largestNum;
 static int naturalSum;
 static int totalNumbersSum;
 public static void main(String args[]) {

  int[] arr = {
   4,
   2,
   6,
   5,
   3,
   1,
   8,
   12,
   9,
   11,
   7
  };
  largestNum = findLargestNumber(arr);
  naturalSum = (largestNum * (largestNum + 1)) / 2;

  for (int i = 0; i < arr.length; i++) {
   totalNumbersSum = totalNumbersSum + arr[i];
  }

  missNum = naturalSum - totalNumbersSum;
  System.out.println("Missing number is " + missNum);

 }
 public static int findLargestNumber(int[] arr) {
  int temp;
  for (int i = 0; i < arr.length - 1; i++) {
   if (arr[i] > arr[i + 1]) {
    temp = arr[i + 1];
    arr[i + 1] = arr[i];
    arr[i] = temp;
   }
  }
  return arr[arr.length - 1];
 }
}