4
$\begingroup$

Given a sorted array of positive integers that is guaranteed to have some unique entry that occupies more than $1/3$ of the entries, is there an algorithm to determine this entry in $O(1)$ time?

Some remarks:

(1) If we replaced $1/3$ with $1/2$, then by checking the first, middle, and last entries of the array, we obtain such a constant time algorithm.

(2) There is a $O(\log n)$ time algorithm obtained by looking at the entries of the array whose indices cut the array into three equal pieces and then doing a binary search for each of these entries to find its first/last appearance in the array.

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
2
$\begingroup$

I think it is more difficult. If your array has 3n elements then you could have n times x and n+1 times y, and the solution is y. So even if you find x and y, you then need to prove that y occurs n+1 and not n times, and x occurs n and not n+1 times. That's probably done with binary search, taking O (log n) steps.

Improve this answer
$\endgroup$
2
  • $\begingroup$ [n × x & n+1 × y], and the solution is y Why y? In n+1 × x & n+2 × y, can it be x? $\endgroup$
    – greybeard
    Commented Dec 12, 2023 at 19:03
  • $\begingroup$ The question was “more than a third”. N out of 3n is not “more than one third”. Yes, sometimes you may have two answers. $\endgroup$
    – gnasher729
    Commented Dec 13, 2023 at 0:24
1
$\begingroup$

I was staring at this question for too long thinking "what's the catch?". But I think I got it

If input array contains 2 entries such that one occupies n/3 entries and the other n/3-1 - then the only way to distinguish between them would be determining exact borders of their intervals - and that's $O(\log n)$

same applies for all fractions below 1/2

fractions above 1/2 don't have the problem, since you can't fit 2 such intervals
and $n/2 - O(f(n))$ is the special case that only has limited placement possibilities, thus needing $O(\log f(n))$

Improve this answer
$\endgroup$
1
  • $\begingroup$ You don't need the exact boundaries, but determining that one is indeed >n/3 takes the same order of operations. $\endgroup$
    – greybeard
    Commented Dec 13, 2023 at 7:40
0
$\begingroup$

No, there is no $O(1)$ time algorithm.

In the $1/2$ case, we can obtain information when the following occurs:

  1. the middle element is equal to the first element
  2. the middle element is equal to the last element
  3. the middle element is equal to neither the first element nor the last element

In the $1/3$ case, we can obtain information when the following occurs:

  1. the first third element is equal to the first element
  2. the second third element is equal to the last element

But the crux is that unlike the $1/2$ case, in the $1/3$ case we can't use inclusion-exclusion principle on the information above to cover the following:

  1. the first third element is equal to neither the first element nor the last element
  2. the second third element is equal to neither the first element nor the last element

This leaves us with binary search to find the remaining information, which runs in $O(log\ n)$ time.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ the >1/2 case needs no further differentiation: the median is the mode. I think "the thirds elements arguments" should read 1st value < 1st third element's value < 2nd third element's value and 1st third element's value < 2nd third element's value < last value - or just all four values distinct. $\endgroup$
    – greybeard
    Commented Dec 13, 2023 at 7:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.