-3

Find number which is occur more than N/3 times in array. not N/2 times? just look at question first.

Without Using Moore's Algorithms.

YOGENDRA SINGH
  • 118
  • 1
  • 1
  • 18

1 Answers1

-1

You will need to take into account the maximum (What is your worst scenario). Unless you have not checked all elements in your array, 2 can compete till the end.

Lets assume you have the following array:

[1,2,3,1,2,2,1,2]

  • when you are at element 4, 1 is the winner with a count of 2.
  • at element 5, 1 & 2 are equal represented.
  • at element 6, 2 is the winner with a count of 3.
  • etc.

Based on this example you can see you will need to run over all of teh elements one time: O(n)

Aldert
  • 4,209
  • 1
  • 9
  • 23