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

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

Sum of Subsets - Find how many pairs in the given array sum to a given number

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...
Post a Comment
Read more

Flatten Iterator

Problem: Given an iterator of iterators, can you give me back an iterator which flattens the given iterator. Ex : Suppose you are given an iterator which has these objects - "1", "2", "3", , , then the flattened iterator returned by you should have "1", "2", "3", "4", "5", "6", "7", "8", "9". Iterators may be nested to any level. This problem can be solved by implementing a FlattenIterator which takes in the given iterator as an agrument in the constructor and delegating the hasNext() and next() calls to the given iterator using a stack. The given iterator is pushed on to the stack. Nested iterators are pushed on to the stack before traversing and once there are no more elements in the iterator, it is popped from the stack. Here is the code - import java.util.*; /** * User: blogkoder * Date: Jul 28, 2008 * Time: 9:32:39 PM */ public class FlattenIterator implement...
Post a Comment
Read more