How to find the element of an array that is repeated at least N/2 times?

by

As the other users have already posted the algorithm, I won’t repeat that. However, I provide a simple explanation as to why it works:

Consider the following diagram, which is actually a diagram of unpolarized light:

arrows radiating from the centre

Each arrow from the centre represents a different candidate. Imagine a point somewhere on an arrow representing the counter and candidate. Initially the counter is at zero, so it begins in the centre.
When the current candidate is found, it moves one step in the direction of that arrow. If a different value is found, the counter moves one step towards the centre.
If there is a majority value, more than half of the moves will be towards that arrow, and hence the algorithm will end with the current candidate being the majority value.

More Related Contents:

  1. Sorting (Quicksort) ,Partition
  2. Recursive and non-recursive traversal of three degree tree
  3. Fast way to tokenize a string in c
  4. how to show time performance for merge sort? [closed]
  5. Why this C code makes infinite loop?
  6. Efficient Algorithm for Bit Reversal (from MSB->LSB to LSB->MSB) in C
  7. What is the fastest substring search algorithm?
  8. Point in Polygon Algorithm
  9. What common algorithms are used for C’s rand()?
  10. Combine Gyroscope and Accelerometer Data
  11. Power by squaring for negative exponents
  12. Matrix multiplication: Small difference in matrix size, large difference in timings
  13. Enumerate factors of a number directly in ascending order without sorting?
  14. read line by line in the most efficient way *platform specific*
  15. Traverse Matrix in Diagonal strips
  16. Program to print permutations of given elements [closed]
  17. Print all permutation in lexicographic order
  18. Perceptron learning algorithm not converging to 0
  19. Gaussian elimination without result for acceleration
  20. Fastest way to calculate a 128-bit integer modulo a 64-bit integer
  21. Lookups on known set of integer keys
  22. signed and unsigned arithmetic implementation on x86
  23. Sorting an array in C?
  24. Find maximum of three number in C without using conditional statement and ternary operator
  25. Algorithm to find all the exact divisors of a given integer
  26. forwarding (drawing) line in 3d grid
  27. Algorithm to generate bit mask
  28. Which is better way to calculate nCr
  29. Extend a line segment a specific distance
  30. QuickSort and Hoare Partition

Leave a Comment