Algorithms Coded in Java

Problem : G iven an array of size 99 which has integers from 1 to 100 and with no integer being repeated, can you find the integer which is not in the array ? There are many differeny ways of solving this problem. The most efficient solution is to just find the difference between the sum of all integers from 1 to 100 and the sum of all integers in the array. This algorithm has a running complexity of  O (n)  and a space complexity of  O (1)  since it just needs 2 variables to store the sums . Here is the code for this -   /**      * This will find the missing integer in the given array of size 99.      *      * The array has integers between 1 and 100 with one integer      * missing.      *      * @param array - Array of integers b/w 1 and 100 of size 99.      * @return int - the missing integer number.      */     public static int findMissingInteger(int[] array)     {         int sum = 0;          // This has the complexity of O (n)         for (int i = 0; i         {             sum...

Problem : Given an array of integers intArray[] and another integer sum, find how many pairs of numbers in the given array will sum up to the given sum. This problem is one of the most sought after question in interviews. There may be slight variations of this problem. There are many ways to solve this problem. The most efficient solution considering both time and space complexity is the one discussed below - /** * This will find how many pairs of numbers in the given array sum * up to the given number. * * @param array - array of integers * @param sum - The sum * @return int - number of pairs. */ public static int sumOfSubset(int[] array, int sum) {          // This has a complexity of O ( n lg n )         Arrays.sort(array);         int pairCount = 0;         int leftIndex = 0;         int rightIndex = array.length - 1;          // The portion below has a complextiy of         //  O ( n ) in the worst case.         while (array[rightIndex] >= su...