Finding a single number in a list [duplicate]

by

The fastest (O(n)) and most memory efficient (O(1)) way is with the XOR operation.

In C:

int arr[] = {3, 2, 5, 2, 1, 5, 3};

int num = 0, i;

for (i=0; i < 7; i++)
    num ^= arr[i];

printf("%i\n", num);

This prints “1”, which is the only one that occurs once.

This works because the first time you hit a number it marks the num variable with itself, and the second time it unmarks num with itself (more or less). The only one that remains unmarked is your non-duplicate.

More Related Contents:

  1. Expand a random range from 1–5 to 1–7
  2. How to find list of possible words from a letter matrix [Boggle Solver]
  3. How to find all combinations of coins when given some dollar value [closed]
  4. Algorithm to generate anagrams
  5. How to generate Sudoku boards with unique solutions
  6. Efficiently reverse the order of the words (not characters) in an array of characters
  7. Programming Riddle: How might you translate an Excel column name to a number?
  8. Fastest algorithm for circle shift N sized array for M position
  9. How to print all possible balanced parentheses for an expression?
  10. complexity in terms of big O
  11. Find all paths between two graph nodes
  12. Why is the constant always dropped from big O analysis?
  13. How can building a heap be O(n) time complexity?
  14. Is there an O(n) integer sorting algorithm?
  15. Which algorithm is faster O(N) or O(2N)?
  16. find the only unpaired element in the array
  17. How to get a square root for 32 bit input in one clock cycle only?
  18. What algorithm gives suggestions in a spell checker?
  19. How can I measure the similarity between two images? [closed]
  20. Bitwise and in place of modulus operator
  21. Find connected components in a graph [closed]
  22. Calculate largest inscribed rectangle in a rotated rectangle
  23. Two Rectangles intersection
  24. Given two arrays a and b .Find all pairs of elements (a1,b1) such that a1 belongs to Array A and b1 belongs to Array B whose sum a1+b1 = k
  25. Examples of Algorithms which has O(1), O(n log n) and O(log n) complexities
  26. How to cartoon-ify an image programmatically?
  27. Is there any fast method of matrix exponentiation?
  28. Optimized low-accuracy approximation to `rootn(x, n)`
  29. What are probabilistic data structures?
  30. Connected Component Labeling – Implementation

Leave a Comment