Skip to main content

Find missing integer problem

Problem : Given 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 += array[i];
        }

        int sumOneToHundred = (100 * 101)  / 2;

        return sumOneToHundred - sum;
    }


Labels:

Comments

Post a Comment

Popular posts from this blog

Find the number of trailing zeroes in the factorial of a given number.

Problem : Find the number of trailing zeroes in the factorial of a given number. This is an interesting problem. Simple way to solve this is to find the factorial of the number and then count the number of trailing zeroes. But there is a more efficient way to find the number of trailing zeroes, without even finding the factorial of the number. The number of trailing zeroes in 5! is 1, 10! is 2, 15! is 3, 20! is 4, but 25! is 6. Then 30! is 7, 35! is 8, 40! is 9, 45! is 10 but 50! is 12 and so on. So for every multiple of 25, the number of zeroes increases by 2 and for every multiple of 5, the number of zeroes increase by 1. So any number less than 5 has 0 trailing zeroes. Any number between 5 and 10 will have 1 zero, between 10 and 15 will have 2 zeroes and so on. Here is a simple C program implementation of this algorithm. import java.io.BufferedReader; import java.io.InputStreamReader; /** * * @author blogkoder * */ public class TrailingZeroesCalculator { public static void m...
3 comments
Read more

Prime Numbers

Problem : Given a number, determine if it is prime or not. To determine if a given number is prime or not, you have to check if the given number is divisible by any number other than 1 and itself. If it is, then it is not a prime number.  * In this algorithm, we check if the given number is less than or equal to zero. If it is then it is not a prime number.  * Next we check to see if the given number is 2.  2 is the only even prime number.  * Then we check if the given number is even. If it is, then it is not a prime number.  * Lastly we divide the given number starting from 3 till the square root of the given number.     /**      * This method checks if the given number n is a prime number or not.      *      * @param n - The number to be checked.      * @return boolean      */     public static boolean isPrime(int n)     {         if (n         {             return false;         }         if (n == 2)         {             return true;         }         if (n % 2 == 0)         {     ...
Post a Comment
Read more

Even Integer Iterator

Problem : Given an iterator of integers, can you give me back another iterator which iterates over the given iterator of integers such that the new iterator gives only even integers. There a couple of different ways to solve this problem. * The first option is to create a new list of integers and add only the even integers from the given iterator and then return an iterator by calling list.iterator(). This has a time complexity of O (n) but also has a space complexity of O (n) in the worst case, which is not desirable. Here is the code for it - public static Iterator<Integer> giveEvenIntegersIterator(Iterator<Integer> iterator) { List<Integer> evenIntegers = new ArrayList<Integer>(); if (iterator != null) { while(iterator.hasNext()) { Integer number = iterator.next(); if (number != null && number % 2 == 0) { evenIntegers.add(number); } } } retu...
Post a Comment
Read more