Thursday 30 July 2015

Find lonely number in array

There is an array ‘arr’ contains n elements, other than one number, remaining numbers all repeated twice. Find the lonely number.

We can solve this problem by using XOR operation.
For a number X.
X^X = 0
X^0 = 0

Since except one number, all other numbers are repeated twice, if we perform X-OR on all numbers of array, final result will be lonely number.
import java.util.Objects;

public class LonelyNumber {

 public static int getLonelyNumber(int arr[]) {
  Objects.nonNull(arr);
  if (arr.length == 0)
   throw new IllegalArgumentException(
     "Array must contain atleast one element");

  int result = arr[0];

  for (int i = 1; i < arr.length; i++) {
   result = result ^ arr[i];
  }

  return result;
 }
}


Following is the junit test case for above program.
import static org.junit.Assert.*;

import org.junit.Test;

public class LonelyNumberTest {
 @Test
 public void test1(){
  int arr1[] = {1};
  int arr2[] = {1, 2, 3, 2, 3};
  int arr3[] = {1, 2, 3, 3, 2, 1, -1};
  
  assertEquals(LonelyNumber.getLonelyNumber(arr1), 1);
  assertEquals(LonelyNumber.getLonelyNumber(arr2), 1);
  assertEquals(LonelyNumber.getLonelyNumber(arr3), -1);
  
 }
}

No comments:

Post a Comment