Home > JAVA, Umum > Lonely Integer

Lonely Integer

Problem:

There are N integers in an array A. All but one integer occur in pairs. Your task is to find out the number that occurs only once.

The solution I choose is using XOR operator. XOR operator have following characteristic:

  1. x (+) 0 = x
    XORing with 0 gives you back the same number.
    Thus, 0 is the identity for XOR.
  2. x (+) 1 = \x
    XORing with 1 gives you back the negation of the bit. Again, this comes from the truth table. For bitwise XOR, the property is slightly different: x ^ ~0 = ~x .
    That is, if you XOR with all 1’s, the result will be the bitwise negation of x.
  3. x (+) x = 0
    XORing x with itself gives you 0.
    That’s because x is either 0 or 1, and 0 (+) 0 = 0 and 1 (+) 1 = 0.
  4. XOR is associative.
    That is: (x (+) y) (+) z = x (+) (y (+) z).
    You can verify this by using truth tables.
  5. XOR is commutative.
    That is: x (+) y = y (+) x.
    You can verify this by using truth tables.

note: (+) is symbol for XOR operator.

Java code:


public class LonelyInteger {

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

int _a_size = Integer.parseInt(in.nextLine());
int[] _a = new int[_a_size];
int _a_item;
String next = in.nextLine();
String[] next_split = next.split(" ");

for(int _a_i = 0; _a_i < _a_size; _a_i++) {
_a_item = Integer.parseInt(next_split[_a_i]);
_a[_a_i] = _a_item;
}

res = lonelyinteger(_a);
System.out.println(res);
}

static int lonelyinteger(int[] a) {
int b = 0;
for(int i=0; i < a.length; i++) {
b ^= a[i];
}
return b;
}
}

Result for input “1 2 1”:

LonelyInteger

Main part is


static int lonelyinteger(int[] a) {
int b = 0;
for(int i=0; i < a.length; i++) {
b ^= a[i];
}
return b;
}

We can write b ^= a[i] as b = b^ a[i]

Explanation:

  1. Loop 1
    b = 0 ^ 1
    b = 1 (characteristic no 1)
  2. Loop 2
    b = 1 ^ 2
  3. Loop 3
    b =b ^ 1 = (1 ^ 2) ^ 1 = 2 ^ ( 1 ^ 1) (characteristic no 4 & 5)
    b = 2

Source:

https://www.hackerrank.com/challenges/lonely-integer

http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/BitOp/xor.html

  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: