Problem
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
$T$denoting the total
$N$
number of test cases. In each test cases, the first line contains an
integer Ndenoting the size of array. The second line contains N
$N$${A}_{1},{A}_{2},\dots ,{A}_{N}$
spaceseparated integers A1,A2,…,ANdenoting the elements of the
$N$
array. (Nis always odd)
Output:
In each seperate line print number of the person not in
couple.Constraints:
1≤T≤30
$1\le T\le 30$1≤N≤500
$1\le N\le 500$1≤A[i]≤500
$1\le A[i]\le 500$N%2=1
$N\mathrm{\%}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:

How can I further improve my approach?

Is there a better way to solve this question?

Are there any grave code violations that I have committed?

Can space and time complexity be further improved?

Is my code very redundant?
Solution
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 ifcondition
 repeated traversal of the container (
contains
andindexOf
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 🙂
2. Is there a better way to solve this question?
4. Can space and time complexity be further improved?
Your approach takes O(n2)
$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)
$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)
$O(n)$space.
The intended approach takes O(n)
$O(n)$time and O(1)
$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);
}
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 “trywithresources” 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 addifnotpresent and removeifpresent operations. This has to be done once per input value, resulting in O(n)
$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)
$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 “oneliner” 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));
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
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.