Algorithm to find the smallest non negative integer that is not in a list

Related searches

Given a list of integers, how can I best find an integer that is not in the list?

The list can potentially be very large, and the integers might be large (i.e. BigIntegers, not just 32-bit ints).

If it makes any difference, the list is "probably" sorted, i.e. 99% of the time it will be sorted, but I cannot rely on always being sorted.

Edit -

To clarify, given the list {0, 1, 3, 4, 7}, examples of acceptable solutions would be -2, 2, 8 and 10012, but I would prefer to find the smallest, non-negative solution (i.e. 2) if there is an algorithm that can find it without needing to sort the entire list.

One easy way would be to iterate the list to get the highest value n, then you know that n+1 is not in the list.

Edit:

A method to find the smallest positive unused number would be to start from zero and scan the list for that number, starting over and increase if you find the number. To make it more efficient, and to make use of the high probability of the list being sorted, you can move numbers that are smaller than the current to an unused part of the list.

This method uses the beginning of the list as storage space for lower numbers, the startIndex variable keeps track of where the relevant numbers start:

public static int GetSmallest(int[] items) {
    int startIndex = 0;
    int result = 0;
    int i = 0;
    while (i < items.Length) {
        if (items[i] == result) {
            result++;
            i = startIndex;
        } else {
            if (items[i] < result) {
                if (i != startIndex) {
                    int temp = items[startIndex];
                    items[startIndex] = items[i];
                    items[i] = temp;
                }
                startIndex++;
            }
            i++;
        }
    }
    return result;
}

I made a performance test where I created lists with 100000 random numbers from 0 to 19999, which makes the average lowest number around 150. On test runs (with 1000 test lists each), the method found the smallest number in unsorted lists by average in 8.2 ms., and in sorted lists by average in 0.32 ms.

(I haven't checked in what state the method leaves the list, as it may swap some items in it. It leaves the list containing the same items, at least, and as it moves smaller values down the list I think that it should actually become more sorted for each search.)

Find the smallest positive number missing from an unsorted array , Given a sorted array of n distinct integers where each integer is in the range from 0 to m-1 and m > n. Find the smallest number that is missing from the array. In this method, we modify the standard Binary Search algorithm to Smallest prime number missing in an array � Find the Missing Number � Find� Find the smallest positive number which can not be represented by given digits Find the smallest positive integer value that cannot be represented as sum of any subset of a given array k-th missing element in an unsorted array

Find the smallest missing number, Then go through the list and find the first pair of numbers v_i and v_{i+1} that are not consecutive. Return v_i + 1. To get the smallest non-negative integer (based � Given a sorted array of distinct non-negative integers, find smallest missing element in it. For example, Input: A[] = [0, 1, 2, 6, 9, 11, 15] Output: The smallest missing element is 3

Unless it is sorted you will have to do a linear search going item by item until you find a match or you reach the end of the list. If you can guarantee it is sorted you could always use the array method of BinarySearch or just roll your own binary search.

Or like Jason mentioned there is always the option of using a Hashtable.

Algorithm to find the smallest non negative integer that is not in a list , Hey Serveriev, We're looking for the smallest missing non-negative integer in these arrays. Since the array you provided starts with 11, this� I need to find the kth smallest element in an unsorted array of non-negative integer. kth smallest element is the minimum possible n such that there are at least kth elements <= n. The rub here is that the array is read only so it can't be modified.

"probably sorted" means you have to treat it as being completely unsorted. If of course you could guarantee it was sorted this is simple. Just look at the first or last element and add or subtract 1.

Find the Smallest Missing Integer in an Array, given an array a of n integers, returns the smallest positive integer java How would you find the smallest non-negative integer that does not occur in the list? FOLLOW-UP: Your algorithm has to run on a computer with, say, 1GB of memory. This is not only limited to computer science but in every task, we do in our daily life, we use an algorithm. Now, to find the smallest number between the three given numbers we will compare each number with each other until we find the smallest one. Step 1: Input three numbers and store it in a,b,c. Step 2: Check if a < b, then min = a, else min = b

I got 100% in both correctness & performance, You should use quick sorting which is N log(N) complexity. Here you go...

    public int solution(int[] A) {
    if (A != null && A.length > 0) {
        quickSort(A, 0, A.length - 1);
    }

    int result = 1;
    if (A.length == 1 && A[0] < 0) {
        return result;
    }

    for (int i = 0; i < A.length; i++) {
        if (A[i] <= 0) {
            continue;
        }
        if (A[i] == result) {
            result++;
        } else if (A[i] < result) {
            continue;
        } else if (A[i] > result) {
            return result;
        }
    }

    return result;
}

private void quickSort(int[] numbers, int low, int high) {
    int i = low, j = high;
    int pivot = numbers[low + (high - low) / 2];

    while (i <= j) {
        while (numbers[i] < pivot) {
            i++;
        }
        while (numbers[j] > pivot) {
            j--;
        }

        if (i <= j) {
            exchange(numbers, i, j);
            i++;
            j--;
        }
    }
    // Recursion
    if (low < j)
        quickSort(numbers, low, j);
    if (i < high)
        quickSort(numbers, i, high);
}

private void exchange(int[] numbers, int i, int j) {
    int temp = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = temp;
}

Find the Smallest Integer Not in a List, The idea is, not to do complete quicksort, but stop at the point where pivot itself is k’th smallest element. Also, not to recur for both left and right sides of pivot, but recur for one of them according to the position of pivot. The worst case time complexity of this method is O(n 2), but it works in O(n) on average.

The beauty of this solution is the number of times it loops is equal to the number of set bits in a given integer. 1 Initialize count: = 0 2 If integer n is not zero (a) Do bitwise & with (n-1) and assign the value back to n n: = n&(n-1) (b) Increment count by 1 (c) go to step 2 3 Else return count

A simple solution is to use two nested loops. The outer loop picks a starting element, the inner loop considers all elements (on right side of current start) as ending element. Whenever sum of elements between current start and end becomes more than the given number, update the result if current length is smaller than the smallest length so far.

Give an $ O(1) $ algorithm to find the largest number in $ A $. Suppose you do not know what $ k $ is. Give an $ O(\lg n) $ algorithm to find the largest number in $ A $. For partial credit, you may give an $ O(n) $ algorithm. (Solution 4.31) 4-32. Consider the numerical 20 Questions game. In this game, Player 1 thinks of a number in the range

Comments
  • Do you need the lowest (positive) integer that is not in the list or any integer that is not in the list?
  • You want to find the lowest, positive integer not in the list? Any specified integer? Which one?
  • "probably sorted" might mean that sorting it fully will be very quick. Depending on the algorithms for "not sorted" and "sorted" lists, this might be worth it.
  • If items = {1, 2, 3}, your solution returns 0. But wasn't the requirement that the number had to be positive?
  • Not true: there are algorithms which perform much better under the assumption of sorted input, and marginally worse if the input turns out not to be sorted after all (behaviour inverse to QuickSort, which performs worst on sorted input).
  • This is the only solution that gets 100% for both correctness and performance on the Codility demo test. This should be the accepted answer.
  • I have been wondering about those answers popping up, which refer to getting 100% and now you are talking about a specific test. Is this question being linked from some outside coding test?
  • There is a website called Codility, which some companies use to do attitudinal tests for people who wanna work for them. The website has a very useful demo test, which you can take a look at here: link. The 100% results in correctness and accuracy, as well as the code I posted refer to this very demo test. @BasselKh's answer from 5 years ago also refers to this.
  • Ah, I see. Thank you.
  • Simply traverse the list from 0 to last element. If all elements found then just take n + 1 element. Some what not clear to me what you're trying to say in second paragraph.