2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ LinkedList should be faster than ArrayList for adding and removing items \$\endgroup\$ – Krzysztof Majewski Aug 1 '18 at 9:34
  • \$\begingroup\$ and still not the right tool for this job... \$\endgroup\$ – Vogel612 Aug 1 '18 at 9:40
8
\$\begingroup\$

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 :)

\$\endgroup\$
  • 2
    \$\begingroup\$ As a micro-optimisation, the contains check can be eliminated by using the boolean return value of either add or remove. E.g. if (!alone.add(elem)) alone.remove(elem);. \$\endgroup\$ – Peter Taylor Aug 1 '18 at 10:53
  • \$\begingroup\$ Thanks, @Vogel612 for your advice. I will try to use Streams for sure. \$\endgroup\$ – Anirudh Thatipelli Aug 1 '18 at 12:18
4
\$\begingroup\$

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);
            }
\$\endgroup\$
  • \$\begingroup\$ For those who don't know: If you XOR a number A with any other number B twice, you get A again. If you XOR 0 with a number, you get that number. You can chain these operations in any order (commutativity), so for example, 0 xor 3 xor 4 xor 3 equals 0 xor 4 xor 4 xor 3, which is 3, because 0 xor 4 xor 4 is 0 xor twice with the same value and 0 xor 3 equals 3. Another way to explain it is that 4 xor 4 equals 0, this 0 xor 4 xor 4 xor 3 equals 0 xor 0 xor 3, so it ends up being 3. \$\endgroup\$ – DarkWiiPlayer Aug 1 '18 at 11:09
  • \$\begingroup\$ @Peter Taylor, thanks for you code-review. I will keep in mind to follow your suggestions. \$\endgroup\$ – Anirudh Thatipelli Aug 3 '18 at 14:23
  • \$\begingroup\$ @DarkWiiPlayer, that's a really cool trick. Bit manipulation makes a lot of tasks easy. \$\endgroup\$ – Anirudh Thatipelli Aug 3 '18 at 14:24
4
\$\begingroup\$

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));
\$\endgroup\$
  • \$\begingroup\$ Thanks for pointing out Bitset and Streams. Being new to Java, I was unaware of these powerful features that this language has to offer. \$\endgroup\$ – Anirudh Thatipelli Aug 3 '18 at 14:31
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Passing Scanner to getAloneNum method doesn't look like a good idea because the method should do only one job, and that's to find the lone number, else it won't be reusable. \$\endgroup\$ – Ankit Soni Aug 1 '18 at 10:18
  • \$\begingroup\$ @AnkitSoni I don't see how wasting memory needlessly in favor of reusability is a good thing, specially when there's no indication that the method will ever be reused for anything. If so, it is still trivial to change it to work with an array or add a further step of abstraction and make it work with an iterator, which could be used both for an array and a stream (without reading said stream into an array first). \$\endgroup\$ – DarkWiiPlayer Aug 1 '18 at 10:34
  • \$\begingroup\$ Or you could just implement a new set object that allows to "toggle" values. Then you could move the loop into the main program entirely. \$\endgroup\$ – DarkWiiPlayer Aug 1 '18 at 10:39
1
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ java.util.BitSet is not sparse, but the size required is heavily restricted by the challenge specification. \$\endgroup\$ – Peter Taylor Aug 1 '18 at 10:49
  • \$\begingroup\$ @PeterTaylor Well, technically, that isn't specified. The numbers need not be sequential, so you could get 1 2 2 1 99999999999 and it would still fit the spec. Then again, the spec doesn't even specify if the numbers are rational, so I guess it's just a poorly written challenge. \$\endgroup\$ – DarkWiiPlayer Aug 1 '18 at 11:19
  • \$\begingroup\$ I am sorry but can you elaborate on your solution more. I am just a beginner. \$\endgroup\$ – Anirudh Thatipelli Aug 1 '18 at 12:24
  • 2
    \$\begingroup\$ Direct quote: \$1 \leq A[i] \leq 500\$ \$\endgroup\$ – Peter Taylor Aug 1 '18 at 12:48
  • 2
    \$\begingroup\$ Another direct quote: _N_ space-separated integers (my emphasis). \$\endgroup\$ – Toby Speight Aug 1 '18 at 12:56
0
\$\begingroup\$

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;
    }
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please edit it to explain your reasoning (how your solution works and how it improves upon the original) so that everyone can learn from your thought process. \$\endgroup\$ – Toby Speight Aug 2 '18 at 14:47

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.