17
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ It doesn't seem to work for this input: assertFalse(Main.findSum(new int[] { 17, 4, 1, 5, 4, 1 }, 13)); \$\endgroup\$ – Panayotis Sep 24 '16 at 7:43
13
\$\begingroup\$

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!

\$\endgroup\$
  • 2
    \$\begingroup\$ In this context i is also a bad variable name, as it is unclear what relation the index i has to the index start. end would be a better name, or you could use last and change start to first. \$\endgroup\$ – Mark H Apr 9 '15 at 7:35
  • 1
    \$\begingroup\$ Is the unnecessary part even correct? Unless I'm missing something, i += 2; would skip the next element without reason, failing in cases where this next element is necessary to achieve the sum (like Main.findSum(new int[] { 10, 8, 1 }, 9)). \$\endgroup\$ – OxTaz Apr 9 '15 at 16:05
  • \$\begingroup\$ @OxTaz You are right, that does break it. I tried to find a flaw in it, but I must have done something wrong in my testing. May I suggest you write an answer pointing out that flaw? Should earn you some reputation :) \$\endgroup\$ – Simon Forsberg Apr 9 '15 at 16:11
11
\$\begingroup\$

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)
\$\endgroup\$
6
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ This is the wrong answer: try {23,5,4,7,2,11} & sum 20. \$\endgroup\$ – Ben Lim Apr 22 '16 at 2:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.