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