How to find the only number in an array that doesn’t occur twice [duplicate]

by

You can define an integer “result” initialized to 0, and then you do some bitwise operations by applying a XOR logic to all elements in your array.

At the end, “result” will be equal to the only element that appears only one time.

result = 0
for i in array:
  result ^= i
return result

http://en.wikipedia.org/wiki/Bitwise_operation#XOR

For instance, if your array contains the elements [3, 4, 5, 3, 4], the algorithm will return

3 ^ 4 ^ 5 ^ 3 ^ 4

But the XOR operator ^ is associative and commutative, so the result will be also equal to:

(3 ^ 3) ^ (4 ^ 4) ^ 5

Since i ^ i = 0 for any integer i, and i ^ 0 = i, you have

(3 ^ 3) ^ (4 ^ 4) ^ 5 = 0 ^ 0 ^ 5 = 5

More Related Contents:

  1. How to remove repetition in output results in this code
  2. Write a program that takes an array/arraylist of integer and finds longest sub array/arraylist whose entries are equal [closed]
  3. Finding the max/min value in an array of primitives using Java
  4. Connect 4 check for a win algorithm
  5. Quickest way to find missing number in an array of numbers
  6. Finding the second highest number in array
  7. Java, find intersection of two arrays
  8. Java, Shifting Elements in an Array
  9. Find duplicate element in array in time O(n)
  10. All possible combinations of an array
  11. Flatten nested arrays in java
  12. Generate Random Numbers in Array [duplicate]
  13. find an element in a sorted matrix [duplicate]
  14. Interview question – Search in sorted array X for index i such that X[i] = i
  15. JAVA ArrayIndexoutofBoundException issue
  16. Graph theory puzzle about connectivity?
  17. How to check if an integer is in a set of given ranges? [closed]
  18. Difference between int[] array and int array[]
  19. How to split a String by space
  20. NullPointerException when Creating an Array of objects [duplicate]
  21. How to parse JSON Array (Not Json Object) in Android
  22. How can I create a stream from an array?
  23. How do I fill arrays in Java?
  24. Determine the size of an InputStream
  25. Time Complexity for Java ArrayList
  26. ‘MergeSort Algorithm’ – What’s the better implementation in JAVA? [closed]
  27. java: Arrays.sort() with lambda expression
  28. Can SHA-1 algorithm be computed on a stream? With low memory footprint?
  29. Java Smooth Color Transition
  30. Compare two arrays of primitives in Java?

Leave a Comment