15
\$\begingroup\$

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;
}
New contributor
user214225 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
  • 1
    \$\begingroup\$ What have I missed? Just calculate a and b as you have done, then make the set or array (1, -1, 2, -2, ... b, -b) and insert 0 as well if a==1. No need to check if any numbers are already in the set, since it's clearly impossible that they are. Sorry, not offering code because I don't program in Java. It's about five lines of Python. \$\endgroup\$ – nigel222 Dec 4 at 10:40
  • 1
    \$\begingroup\$ Not sure if the assignment is a joke assignment or an intelligence test (or English language test) of sorts. Or maybe they forgot to tell you an extra condition? Array with N unique elements, and the sum must be zero. No other requirement. Thus, the by far easiest solution is to fill the array up to the last-but-one slot with increasing integers starting at zero, i.e. each element's value is its index (those aren't very interesting numbers, but they sure are unique), and sum them up while doing so (basically zero-cost operation). Then negate the sum, and fill that in the last slot. Done. \$\endgroup\$ – Damon 2 days ago
  • \$\begingroup\$ @Damon: That's basically what Slepic did in his answer. \$\endgroup\$ – Brian 2 days ago
8
\$\begingroup\$

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;
}
New contributor
Fred Woods is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
  • \$\begingroup\$ Nice edit (and nice answer). I've smoothed over the edges around codefences in SE's markdown implementation a bit :) \$\endgroup\$ – Vogel612 Dec 2 at 19:28
  • 1
    \$\begingroup\$ The special case for n == 1 is not needed here \$\endgroup\$ – Eric Dec 3 at 9:20
15
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ What makes you think this solution is faster? You're still looping through all N elements to put them into the list right? \$\endgroup\$ – Imus Dec 2 at 9:05
  • 2
    \$\begingroup\$ No I am not looping anything, I let a system function solve most of the problem for me. I dont know if it does any looping on its own... Then I just append one element. I haven't tried this, nor I know Java enough to know how it works in this language. I merely CONJECTURE that it COULD be faster based on my experiences with other languages. \$\endgroup\$ – slepic Dec 2 at 9:14
  • 3
    \$\begingroup\$ Regardless of how the integer sequence is generated, this is clearly the most simple algorithm. An integer range can be generated with IntStream.rangeClosed(startInclusive, endInclusive) but using that here would be overkill. A simple array init and loop to fill it will be the most efficient solution. I'm guessing using system services to create integer ranges is a thing from interpreted languages. There's not much to be gained in Java by doing it in native code. \$\endgroup\$ – TorbenPutkonen Dec 2 at 9:24
  • \$\begingroup\$ @slepic I’m baffled by your conjecture. Even a highly optimised function to generate these consecutive values wouldn’t generally beat a simple loop that does the same. And then you still need to compute the sum of these numbers which, as you note, is a simple equation but nevertheless contains more arithmetic than the naïve solution that just pairs positive and negative numbers, and is thus almost certainly slower. Having to write less code would be a more valid argument (for instance in many languages this would be one or at most two lines of code, e.g. in R or C++). \$\endgroup\$ – Konrad Rudolph Dec 2 at 17:52
  • \$\begingroup\$ I'll note that you don't actually need to treat N=1 as a special case. Since 0 is the empty sum, it's already covered. \$\endgroup\$ – Brian 2 days ago
7
\$\begingroup\$

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++) {
\$\endgroup\$
  • 2
    \$\begingroup\$ "Overly complicated solution" arent you describing exactly OPs solution here? Except he Is doing it in 2 fors where 1 would be enough... \$\endgroup\$ – slepic Dec 2 at 8:19
  • 2
    \$\begingroup\$ Aha sorry, now I see the OP keeps editing his answer to reflect proposed changes and your answer therefore references something that is no longer there. \$\endgroup\$ – slepic Dec 2 at 9:06
6
\$\begingroup\$

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();
}
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ If anyone knows a sane way to avoid creating the range twice, I'm all ears. \$\endgroup\$ – JollyJoker Dec 3 at 10:08
2
\$\begingroup\$

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;
}
New contributor
Jeremy Trifilo is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
  • 1
    \$\begingroup\$ Hey Jeremy, great first post, good job! \$\endgroup\$ – IEatBagels Dec 2 at 16:42
  • 1
    \$\begingroup\$ “in this case, it means to divide by 2” — so why not write size / 2? “[size & 0x01] is equivalent to what everyone else did which was "size % 2 == 1"” — Again, so why not just write size % 2 == 1? There’s no reason to hide the intent you want to express. Not that these are particularly cryptic operations, but I firmly believe in restricting bit operations to when you actually intend to reason about bit manipulations. When in the real of integer arithmetic, use integer arithmetic. Otherwise you’re obfuscating. \$\endgroup\$ – Konrad Rudolph Dec 2 at 18:03
  • 1
    \$\begingroup\$ The problem description specifically required an array of integers. You can't change it to bytes just because it's convenient or efficient. It's also a bit ugly practice to use method parameters as loop counters. \$\endgroup\$ – TorbenPutkonen Dec 2 at 20:11
  • 4
    \$\begingroup\$ Bit shifting is no more efficient than dividing by two. You're adding cognitive load to the reader. \$\endgroup\$ – TorbenPutkonen Dec 2 at 20:15
  • 1
    \$\begingroup\$ “The remainder operator should be reserved for non powers of two.” — There is absolutely no reason for this whatsoever. Using bit operations when you intend to perform regular arithmetic is somewhat common because people think it looks “clever” but that’s a poor justification. Good code expresses intent directly. \$\endgroup\$ – Konrad Rudolph Dec 3 at 8:32
0
\$\begingroup\$

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.

New contributor
user10186512 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$

Your Answer

user214225 is a new contributor. Be nice, and check out our Code of Conduct.

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.