Generate array of integers that sum to zero

Question

Problem

Write a function that, given an integer N (1 ≤ N ≤ 100), returns an array containing N unique integers that sum up to 0. The function can return any such array.
For example, given N = 4, the function could return [1, 0, −3, 2] or [−2, 1, −4, 5]. The answer [1, −1, 1, 3] would be incorrect (because value 1 occurs twice). For N = 3 one of the possible answers is [−1, 0, 1] (but there are many more correct answers).

Any ideas would be much appreciated.
Any better implementation? or any holes in my answer?

Current implementation

public static int[] Solution(int N)
{
    HashSet set = new HashSet();
    int a = N % 2;
    int b = N / 2;

    for (int i = 0; i < b; i++)
    {

        if (!set.contains(b - i))
        {
            set.add(-(b - i));
        }
    }

    if(a != 0)
    {
        set.add(0);
    }

    for (int i = 0; i < b; i++)
    {
        if (!set.contains(b - i))
        {
            set.add((b - i));
        }
    }

    int[] entries = set.stream().mapToInt(Integer::intValue).toArray();
    return entries;
}

Answer 1

You don't need the HashSet, just an array of size N will do. Your requirements fix the result list size.

int[] entries = new int[N];
...
return entries;

You also don't need the checks to see if the value is already in the array because, your loop is making sure of that. An additional index variable to track the location of the insertions could be used to reduce the control logic and thus the cyclomatic complexity of the function.

if (0 != a) {
  entries[0] = 0;
}
for (int i = 0, int j = a; i < N; i++) {
    entries[j++] = (i + 1);
    entries[j++] = -(i + 1);
}

Given the sum of N odd numbers equals N squared, an alternative solution is;

public static int[] Solution(int N)
{
    int[] entries = new int[N];
    int i = 1;
    int j = 1;

    entries[0] = (1 == N) ? 0: (N - 1) * (N - 1);

    while (i < N) {
        entries[i++] = -j;
        j += 2;
    }

    return entries;
}

Answer 2

If you really don't care which combination is result as long as it sums to zero, then I would propose a different approach.

Of course you can name out all integers, fliping between positive and negative, adding zero if N is odd.

[1,-1,2,-2,...., 0]

Or in reverse order

[....,2,-2,1,-1,0]

Or negatives on end

[1,2,,...., 0, ...., -2, -1]

These are basically all the same in terms of the implementation.

But I think I have faster one:

[0]
[1,-1]
[1,2,-3]
[1,2,3,-6]
[1,2,3,4,-10]
[1,2,....,n-1, -1*n*(n-1)/2]

In words, generate [0] for N=1, for N>1 generate consecutive integers from 1 to N-1 and append the negative of their sum (which you get by formula for sum of arithmetic series). I am not a javist, but I believe that there is a function that generates the consecutive integers very effectively. And the last element is computed using a simple formula consisting of 4 arithmetic operations (or 3 if you use n-1 from the consecutive series generator).

EDIT: Notice how my proposed output is asymetric compared to your solution. But as long as the sum of consecutives does not overflow the int data type, it will be fine. And since 1 < N < 101, the sum is at most 4950, this is far from overflow.

Answer 3

Overly complicated solution

The problem description tries to (intentionally?) make the problem look more complicated than it actually is. To get N integers that sum to zero you need a series of N/2 negative integers and N/2 positive integers from -(N/2) to -1 and 1 to (N/2). Add zero if N is odd.

E.g. N = 5: [-2, 2, -1, 1, 0]

Stylistic problems

Please try to follow standard Java naming conventions: method and variable names start with lower case letter. Use final specifier whenever a value is not changed to tell the reader that the value will not change.

public static int[] solution(final int arraySize)

Use parameterized types whenever possible and initialize collections to the exact size if you know it. Avoid single letter variable names as they usually do not convey any information about the purpose of the variable. Instead use names that describe the purpose of the variable.

final HashSet<Integer> result = new HashSet<>(arraySize);

In Java, curly braces are usually placed at the end of the line. When placed on a separate line, they make the code extremely sparse. Use empty lines between code blocks to make logical groups easier to distinguish from each other.

}

if (a != 0) {
    set.add(0);
}

for (int i = 0; i < b; i++) {

Answer 4

At first glance it looked like you're overcomplicating things by first putting your generated numbers into a HashSet to then transform it to an int[]... until I tried to write my own solution that directly works with an array. I found a way to do it, but man was that tricky to get the indices right ...

Given how anoying that was, let's keep your Set based solution and look at how to clean that up a bit instead. Here's the final result I ended up with, I'll go over most of the changes next:

public static int[] solution(int n) {
    Set<Integer> set = new HashSet<Integer>();
    if (n % 2 != 0) {
        set.add(0);
    }
    int halfN = n / 2;
    for (int i = 0; i < halfN; i++) {
        set.add(halfN - i);
        set.add(-(halfN - i));
    }

    return set.stream().mapToInt(Integer::intValue).toArray();
}

• HashSet<Integer>() includes the generic type. That way the compiler can check that the stream.mapToInt(Integer::intValue) will work, since it knows it's working on Integer instead of Object.

• Set<Integer> set = Using weaker interface instead of the HashSet as the variable type. In this case it doesn't matter much, but in general it's better to use the interface that you need. If you ever want to change the implementation you'll only need to update the line where it's created.

• Combined the 2 for loops. Since they're looping over the same index anyway.

• Removed the contains check. You know the set isn't going to contain those elements since the index is different on each loop.

• renamed unclear variables. b doesn't say anything about what it is making it harder to understand later lines that depend on knowing it's half of N. Naming it halfN becomes obvious after my previous scentense. a has been inlined since it's only used once anyway.

• inlined return statement. No real reason to declare a variable for that if you're going to return it right after anyway.

• Capital letters in Java are used for class names and constants (all caps for those). Methods and variable names should start with a small case.

---

Alternatively since you're already looking into streams, you might as well try to generate the numbers using IntStream in the first place. The tricky part is what to do with the 0 in case of an even N.

public static int[] solution(int n) {
    return IntStream.rangeClosed(-n / 2, n / 2)
            .filter(num -> (n % 2 == 1 || num != 0))
            .toArray();
}

Answer 5

The simplest solution for getting N unique integers summing to zero is to generate the n-1 first integers and append their negative sum.

Generate the n-1 first integers: IntStream.range(1,n)

Sum: IntStream.sum()

Concatenate: IntStream.concat()

To avoid writing IntStream over and over, use a static import.

import static java.util.stream.IntStream.*;

Then your method becomes

public static int[] solution(int n) {
    IntStream negativeSum = of(-range(1, n).sum());
    return concat(range(1, n), negativeSum).toArray();
}

Try it online!

Answer 6

Here's a very simple and easy to understand version of the problem. I made adjustments based on criticism, but overall it's the same.

I recommend NOT using a Hashmap, especially for this situation. Container classes have specific uses and generally, your use case won't fully utilize what they are capable of. As such I recommend learning how to write your own container functions and as you can see we accomplished that with very little effort.

The First "IF" statement is checking if 'SIZE' is an ODD number i.e. 1,3,5,7,etc.. If it is we set the last index of our array to 0. Since arrays start at 0, not 1 we have to decrease size by 1 and we do that by doing --SIZE.

Then we keep looping while size >= 2. This is because every time we loop we decrement size by 2 and set each indexing from highest to lowest to a number and a negative number that is half the current size value. The lowest index we can use is 0. So 2 - 2 = 0.

You'll see the following situations

(Size = 100) -> 50, -50, 49, -49, ... 1, -1

(Size = 99) -> 0, 49, -49, 48, -48, ... 1, -1

public static int[] Solution(int size)
{
    int values[] = new int[size];

    if ((size % 2) == 1)
        values[--size] = 0;

    while (size >= 2)
    {
        int number = size / 2;

        values[--size] =  number;
        values[--size] = -number; 
    }

    return values;
}

Answer 7

In addition to the answers given earlier, there's another simple answer based on the knowledge that the sum of sequential integers starting from 1 is a triangle number whose value is n(n + 1)/2:

public static int[] Solution(int n) {
    int[] result = new int[n];

    // The negation of the nth triangular number is -n(n + 1) / 2
    // Our list only goes up to n - 1, and -(n - 1)(n - 1 + 1) = n(1 - n), so:
    result[0] = n * (1 - n) / 2;
    for (int i = 1; i < n; ++i) {
        result[i] = i;
    }

    return result;
}

While in this case there are several other simple and fast solutions, often it might be convenient to find out if there's a solution that can exploit available mathematical knowledge to speed up or simplify calculations.