Given a sequence of positive integers A and an integer T, return true if a continuous sequence of A sums up to exactly T

Question

Here is the source of the question, and my solution is below. Did I determine the worst case correctly? If you find any input where it doesn't work, please let me know.

public class Main {

    /*
     * http://www.careercup.com/question?id=6305076727513088
     * 
     * Worst case: O(2*n)
     * [ 1, 3, 4, 1, 0, 23 ] and k == 23. We have to iterate over the array twice:
     * 
     * 1. We sum up all the elements [0, n - 1], n - the array size
     * 2. We subtract all the elements [0, n - 2]
     */
    static boolean findSum(int[] array, int k) {
        int i = 0;
        int start = i;
        int sum = 0;
        for (; i < array.length;) {
            if (array[i] > k) {
                i += 2;
                start = i;
                sum = 0;
                continue;
            }
            if (sum < k) {
                sum += array[i];
                i++;
            }
            while (sum > k) {
                sum -= array[start];
                start++;
            }
            if (sum == k) {
                return true;
            }
        }
        return false;
    }

}

Unit tests.

import static org.junit.Assert.*;

import org.junit.Test;

public class MainTest {

    @Test
    public void testFindSum() {
        // k exists in the input array

        // It's the first element
        assertTrue(Main.findSum(new int[] { 15, 4, 6, 10, 2, 11 }, 15));
        // It's in the middle
        assertTrue(Main.findSum(new int[] { 1, 4, 15, 10, 2, 11 }, 15));
        // It's the last element
        assertTrue(Main.findSum(new int[] { 1, 4, 0, 10, 2, 15 }, 15));

        // k equals to the sum of a few elements

        // The elements are at the beginning
        assertTrue(Main.findSum(new int[] { 10, 4, 4, 10, 2, 16 }, 14));

        // The elements are at the middle
        assertTrue(Main.findSum(new int[] { 1, 4, 4, 10, 2, 16 }, 14));

        // The elements are at the end
        assertTrue(Main.findSum(new int[] { 1, 4, 4, 1, 1, 13 }, 14));

        // k is the sum of all the elements
        assertTrue(Main.findSum(new int[] { 1, 4, 4, 1, 4 }, 14));

        // There is an element which is greater than k
        // It's in the middle
        assertFalse(Main.findSum(new int[] { 1, 42, 4, 1, 4 }, 14));

        // It's the first element
        assertFalse(Main.findSum(new int[] { 42, 1, 4, 1, 4 }, 14));

        // It's the last element
        assertFalse(Main.findSum(new int[] { 1, 0, 4, 1, 42 }, 14));

        // Last but one
        assertFalse(Main.findSum(new int[] { 1, 0, 4, 144, 12 }, 14));

        // Worst case
        assertTrue(Main.findSum(new int[] { 1, 3, 4, 1, 0, 23 }, 23));

    }

}

GitHub

Answer 1

Approach and complexity

It is a pleasure to tell you this: Excellent!

Your approach is precisely what I had in mind when I read the challenge description (before looking at your code).

Unit tests

Excellent that you have unit tests! Definitely helps in checking if it's possible to clean up your method. My only suggestion would be to make them Parameterized, which should be a lot more helpful if one or more of them fails.

Some simplifications

I was slightly confused by this code at first:

if (array[i] > k) {
    i += 2;
    start = i;
    sum = 0;
    continue;
}

Then I noticed that it checked if the value at the current position in the array was more than the target k. Then I figured: "Why use this as a special case? The rest of the code should be able to handle this." And it does. Removing this part of the code doesn't change a thing on your unit tests either. While I can understand why you are doing this (it probably does help a bit with performance in some cases), I don't think it's worth it. Don't add unnecessary special-cases.

---

Next thing I noticed is that sum < k will always be true. Therefore, that if can be removed and be simply:

sum += array[i];
i++;

And now, speaking of i++, we can transform this for-loop into a traditional for loop, by adding both the initialization and the iteration to it:

for (int i = 0; i < array.length; i++) {

This makes it:

static boolean findSum(final int[] array, final int k) {
    int start = 0;
    int sum = 0;
    for (int i = 0; i < array.length; i++) {
        sum += array[i];
        while (sum > k) {
            sum -= array[start];
            start++;
        }
        if (sum == k) {
            return true;
        }
    }
    return false;
}

Nitpicks

k is a bad variable name. target or targetSum would be better.

I am not a big fan of int start = i; in your original code. start is not dependent on i at all. They start at the same value, sure, but it's more clear to set start = 0;

Your method lacks an accessibility modifier, you probably want to make it a public method.

Overall

Well done!

Answer 2

I had a bit of a longer answer in the works, but Simon's answer covers almost every point I intended to cover.

The one thing I can add is this:

Variable's scope should be as limited as possible.

Variable's scope should be no wider than necessary.

We don't use start or sum outside of the for loop, so let's declare them in the initialization statement of the for loop, making their scope as narrow as possible.

for (int sum = 0, start = 0, i = 0; i < array.length; ++i) { // ...

---

Also, I think the method name needs some work. findSum makes me think the method will in some way sum up the arguments and return an int, so that it returns a boolean is confusing. We could try on the following method name and see if it fits:

public static boolean containsSummationSequence(final int[] array, final int targetSum)

Answer 3

The unnecessary part (as explained in Simon's answer) also has a flaw:

    if (array[i] > k) {
        i += 2;
        start = i;
        sum = 0;
        continue;
    }

Here, i += 2; not only ignores the current element as intended, but also skips the next element. So, it will fail if this next element is necessary to achieve the sum, like:

assertTrue(Main.findSum(new int[] { 10, 8, 1 }, 9)); // Fails: 8 is skipped
assertTrue(Main.findSum(new int[] { 20, 15 }, 15));  // Fails: 15 is skipped

Answer 4

One suggestion for your method signature, you can consider using varargs on the integer sequence, so that you leave the implicit int[] declaration to the compiler/JVM:

public static boolean findSum(int targetSum, int... array) {
    ...
}

To add on to Simon's point of parameterized testing, I have previously compared this feature for both JUnit and TestNG frameworks, hopefully it gives you a better idea of how it can be done: Match Simple Sentence or Partial Sentence

Answer 5

Here is another possible solution, however it seems logically equivalent to Simon's answer.

public static boolean findSum(int[] array, int k) {
  int a = 0, b = 0, sum = 0;

  while(b < array.length) {
    if(sum < k) sum += array[b++];
    else if(sum > k) sum -= array[a++];
    else return true;
  }
  return sum == k;
}