Clever Geek Handbook

Algorithm for computing TripleSum O (n), Java

The challenge is to come up with an algorithm that takes an array of non-negative integers and returns a boolean value depending on whether the array contains 3 numbers up to 225.

The hard part is O (n) time.

Does anyone have any idea?

+3


source to share


2 answers


Just thinking about the bypass ATM as I'm not on the computer right now, but what about:

Scanning by numbers after recording each of them - reset more than 225.

Perform one counting pass to determine the answer.

It should be O (n) when we go through the initial transfer once, the rest is O (225) which disappears.



Added - now I have a computer.

I missed some edge cases, but this looks like a fair implementation of the algorithm:

boolean canAdd3ToMakeX(int[] v, int x) {
    // How many of each number.
    int[] counts = new int[x];
    // O(n) part.
    for (int i = 0; i < v.length; i++) {
        if (v[i] >= 0 && v[i] < x) {
            counts[v[i]] += 1;
        }
    }
    // O(k) part. :) - NOT the most efficient - but the most obvious.
    for (int a = 0; a < x; a++) {
        for (int b = 0; b < x; b++) {
            for (int c = 0; c < x; c++) {
                if (a + b + c == x && counts[a] > 0 && counts[b] > 0 && counts[c] > 0) {
                    return true;
                }
            }
        }
    }

    return false;
}

private void test(int[] t) {
    System.out.println("Can - " + Arrays.toString(t) + " = " + canAdd3ToMakeX(t, 225));
}

public void test() {
    test(new int[]{1, 2, 3, 4, 5, 5, 5, 5, 5});
    test(new int[]{1, 2, 222});
    test(new int[]{100, 100, 25});

}

This certainly gives the correct answer to my test cases, but I believe there are problems with my solution that would make it unacceptable for presentation as homework. I leave the solution to these problems to the student (hint: try it test(new int[]{100, 25})

.

+4


source


Since it may not be entirely clear how to do this from @ OldCurmudgeon's answer, here's a bit of explanation in detail:

  • Since we only have non-negative numbers, we only need to consider numbers from 0

    to 225

    , which means we can Bucketsort in O (n) because there is a constant number of buckets to solve (just create an array of 226 lists and add the value of the value i

    to i-th list or whatever your favorite bucketsorting way).
  • After that, make a sorted array of values ​​between 0

    and 225

    . Correct the pointer pointer = array.length - 1

    for the largest sum element in array[pointer]

    . Now check O (n) if it is possible to create 225 - array[pointer]

    (the next point of the pool explains how to do it) - if you can, then there are three values ​​in your array that add up to 225

    , if you cannot, recurse, decrementing pointer

    until it points to next lower value.
  • To check an array in O (n), whether it contains two values a

    and b

    such that a + b = c

    , you first put the contents of the array into a hashmap to count their multiplicities, then you loop through the array and for each entry a[i]

    , you check if c - a[i]

    the hashmap is and if a[i] = c - a[i]

    , you are checking if this value happens at least twice. If you find such an entry at some point, you can add the two values ​​to get it c

    , if you don't, you can't.

Note that if we fix the constant value we want to sum, we can actually allow an arbitrary number of non-negative terms and still end up using O (n) by applying this approach inductively. All of this is of course the expected time due to the hashing, and also: for large values ​​(which I think no one would count 225

here), calling this O (n) approach is technically correct, but the eyewash bit.



Another way to do what OldCurmudgeon suggested is to sort and then try everything (worst case, depending on how often the values ​​appear) 225 ^ 3 possibilities and see if any of them work. It will also be O (n) as it is sort dominated and O (225 ^ 3) = O (1), and also generalizes to sums with an arbitrary fixed number of terms, but depending on the number of terms and the value we want to sum, this maybe even worse than the above with hashing.

+1


source






More articles:


All Articles