It's an exercise I was given:
We say array of numbers $A$ is geometric if:

  • It has size $n=2^k-1$
  • It has $\log n$ distinct numbers
  • For each $0\leq i \leq k-1$ there exists an element in the array that appears exactly $2^i$ times.

    For example: $[8,5,2,5,5,5,8], k=3$
    I need to sort the array in $\mathcal{O}(n)$ time and space.
    I can solve it by using any algorithm that finds majority element in linear time.
    My question is, can we solve it without finding using algorithm that finds majority element?

  • $\endgroup$
    • 1
      $\begingroup$ counting sort is the obvious answer. $\endgroup$ – ratchet freak Sep 8 '17 at 13:54
    • $\begingroup$ Can you elaborate please? $\endgroup$ – sel Sep 8 '17 at 14:00
    • $\begingroup$ en.wikipedia.org/wiki/Counting_sort $\endgroup$ – ratchet freak Sep 8 '17 at 14:05
    • $\begingroup$ If they are integers then count sort. Unless the range is bigger than n it will be O(n) space. $\endgroup$ – paparazzo Sep 8 '17 at 14:45
    • $\begingroup$ We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Sep 8 '17 at 20:46

    Your Answer

    By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

    Browse other questions tagged or ask your own question.