Alone in a Couple implementation in Java

Question

In a party everyone is in couple except one. People who are in couple have same numbers. Find out the person who is not in couple.

Input:

The first line contains an integer \$T\$ denoting the total number of test cases. In each test cases, the first line contains an integer \$N\$ denoting the size of array. The second line contains \$N\$ space-separated integers \$A_1, A_2, \ldots, A_N\$ denoting the elements of the array. (\$N\$ is always odd)

Output:

In each seperate line print number of the person not in couple.

Constraints:

\$ 1 \leq T \leq 30\$

\$ 1 \leq N \leq 500\$

\$ 1 \leq A[i] \leq 500\$

\$ N \% 2 = 1\$

Example:

Input:

1 

5 

1 2 3 2 1

Output:

3

My approach:

/*package whatever //do not write package name here */

import java.util.Scanner;
import java.io.IOException;
import java.util.List;
import java.util.ArrayList;

class GFG {

    private static int getAloneNum (int[] arr) {
        List<Integer> alone = new ArrayList<>();

        for (Integer elem : arr) {
            if (!(alone.contains(elem))) {
                alone.add(elem);
            }
            else {
                alone.remove(alone.indexOf(elem));
            }
        }

        return alone.get(0);
    }

    public static void main (String[] args) {
        Scanner sc = new Scanner (System.in);
        int numTests = sc.nextInt();

        for (int i = 0; i < numTests; i++) {
            int size = sc.nextInt();
            int[] arr = new int[size];

            for (int j = 0; j < size; j++) {
                arr[j] = sc.nextInt();
            }

            System.out.println(getAloneNum(arr));
        }
    }
}

I have the following questions with regards to the above code:

1. How can I further improve my approach?

2. Is there a better way to solve this question?

3. Are there any grave code violations that I have committed?

4. Can space and time complexity be further improved?

5. Is my code very redundant?

Reference

Answer 1

You are using a pretty nice idea here. You store things you've seen once and remove them when you've seen them a second time. To do so you're using a List.

Instead of a List you should be using a Set though. Lists are not optimized for contains checks. Also ArrayList has a pretty expensive remove operation. Let's rewrite the getAloneNum with a Set:

private static int getAloneNum(int[] arr) {
    Set<Integer> alone = new HashSet<>();
    for (int elem : arr) {
        if (alone.contains(elem)) {
            alone.remove(elem);
        } else {
            alone.add(elem);
        }
    }
    return alone.iterator().next();
}

Note that this implementation avoids the following things:

• Unnecessary negation in the if-condition
• repeated traversal of the container (contains and indexOf traverse the full list)

I also personally prefer to not have a space before the opening parenthesis, but YMMV :)

As a challenge for java 8 you could try to rewrite this to use as little memory as possible by using a Stream and handling the input as it comes instead of saving it into an array :)

Answer 2

2. Is there a better way to solve this question?
4. Can space and time complexity be further improved?

Your approach takes \$O(n^2)\$ time (because at least one of searching or removing elements from a list will take time linear in the length of the list) and \$O(n)\$ space (because the length of the list may be half as long as the length of the input).

The suggestion of using a HashSet will, under reasonable assumptions, take \$O(n)\$ time and \$O(n)\$ space.

The intended approach takes \$O(n)\$ time and \$O(1)\$ space and consists of accumulating the numbers seen so far using ^ (xor). This operator has lots of nice properties: in particular it is commutative (a ^ b == b ^ a) and associative ((a ^ b) ^ c == a ^ (b ^ c)), and every value is its own inverse (a ^ a == 0).

---

5. Is my code very redundant?

There's only one thing which looks truly redundant to me:

            if (!(alone.contains(elem))) {
                alone.add(elem);
            }
            else {
                alone.remove(alone.indexOf(elem));
            }

If elem is already in the array then it scans once to test contains and a second time to find indexOf. List is the wrong data structure for this problem, but if you were e.g. required to use it in an interview question this would be less redundant as

            int index = alone.indexOf(elem);
            if (index == -1) {
                alone.add(elem);
            }
            else {
                alone.remove(index);
            }

Answer 3

Some code review comments not mentioned by other:

• Unnecessary import:

You have import java.io.IOException; but you are neither catching nor throwing an IOException.

• Possible resource leak

When you open a Closable resource, it is a good habit to .close() it when you are done. This can be automatically done if you use a "try-with-resources" statement:

try (Scanner sc = new Scanner(System.in)) {
   // ... use scanner in here
}
// Scanner is automatically closed here.

---

Better (or at least other) ways to solve the problem:

You can use a BitSet to improve the time and space complexity of the algorithm. With 1 <= A[i] <= 500, the BitSet only needs 64 bytes of storage. Setting, clearing and (in this case) toggling bits are very fast \$O(1)\$ operations. You don't need to ask whether the element has been encountered before, adding it if it hasn't and removing it if is has; just flipping the corresponding bit performs the add-if-not-present and remove-if-present operations. This has to be done once per input value, resulting in \$O(n)\$. At the end, the sole remaining bit can be found with .nextSetBit(0), which is a \$O(n/64)\$ search operation, yielding an overall \$O(n)\$ algorithm.

private static int getAloneNum (int[] arr) {
    BitSet alone = new BitSet(501);

    for (int elem : arr)
        alone.flip(elem);

    return alone.nextSetBit(0);
}

---

Thinking about streams, it occurred to me a BitSet would also make a good Collector. BitSet::flip works as an accumulator, and BitSet::xor will work as a combiner. This allows the following "one-liner" solution:

import java.util.BitSet;
import java.util.Scanner;

public class Alone {

    public static void main(String[] args) {

        try(Scanner sc = new Scanner(System.in)) {

            int num_tests = sc.nextInt();
            for(int test=0; test < num_tests; test++) {

                int n = sc.nextInt();
                System.out.println(sc.tokens()
                        .limit(n)
                        .mapToInt(Integer::valueOf)
                        .collect(BitSet::new, BitSet::flip, BitSet::xor)
                        .nextSetBit(0));
            }
        }
    }
}

---

Or, inspired by @PeterTaylor's answer, the BitSet can be skipped entirely, and a simple int used as the accumulator!

                System.out.println(sc.tokens()
                        .limit(n)
                        .mapToInt(Integer::valueOf)
                        .reduce(0, (a,b) -> a ^ b));

Answer 4

Seems like a pretty good solution to the problem. There's one thing I'd have done differently though: When you read the test, you first parse it into an array before passing it to the function

for (int j = 0; j < size; j++) {
    arr[j] = sc.nextInt();
}

Instead you could just pass the scanner and the length to getAloneNum(Scanner sc, int numTests)

Then change the loop inside the function to

for (int i = 0; i < numTests; i++) {
    int elem = sc.nextInt();
    if (alone.contains(elem) {
        alone.remove(alone.indexOf(elem));
    } else {
        alone.add(elem);
    }
}

Also I guess you could use a Set<Integer> instead of an ArrayList<Integer> to improve lookup time a bit. EDIT: Vogel612 provided a good example for this in their answer

Answer 5

The correct way of solving this is with a sparse bit set. Sadly there is none in the standard jdk that I know of. So for simplicity HashSet is the closest we get. See the answer from Vogel612 for how to use it.

The lines of numbers could be LONG. If the input is

   112233445566...N

your program start by allocating a array of size 2*n+1. A better approach is to read the file and add and remove them as you go. In this case you would only ever have 2 elements in your hash set at the most.

Answer 6

The best method to solve this problem is to take XOR of every element in the array. This method does not require any additional space and the time complexity is O(N).

Edit : The solution works based on 2 XOR properties:

1. a^a = 0 (XOR of 2 same number is always 0).
2. a^0 = a (XOR of a number with 0 is the number itself).

So all the couples having same number will result 0 when applying XOR operator. This 0 when applied to the single number will output the single number.

In your solution, you have used extra space which can be avoided.

    private static int getAloneNum (int[] arr) {
         int result = 0;
         for(int i = 0; i < arr.length; ++i)
              result ^= arr[i];
         return result;
    }