There is an array of n numbers. One number is repeated n/2 times and other n/2 numbers are distinct

There is an array of n numbers. One number is repeated n/2 times and other n/2 numbers are distinct.Find the repeated number. (Best soln is o(n) exactly n/2+1 comparisons.)

the main problem here is n/2+1 comparisons. i have two solutions开发者_开发技巧 for O(n) but they are taking more than n/2+1 comparisons.

1> divide the numbers of array in groups of three.compare those n/3 groups for any same elements. e.g array is (1 10 3) (4 8 1) (1 1)....so number of comparisons required is 7 which is >n/2+1 i.e 8/2+1=5

2> compare a[i] with a[i+1] and a[i+2] e.g array is 8 10 3 4 1 1 1 1

total 9 comparisons

i appreciate even a little help. thank you

space complexity is O(1).

of course if all other are distinct you only have to compare all pairs. If you find one pair whit two equal numbers you have this number

lets say you have numbers like this (it is just about indexing)

[1,2,3,4,5,6,7,8,9,10]

you then make n/2 + 1 comparisons like this

(1,2),(3,4),(5,6),(7,8),(9,7),(9,8)

if all pairs are distinct you return 10.

Point is then when you compare last 4 remaining numbers (7,8,9,10) you know that among then are at least two same numbers and you have 3 comparisons.

You just need to find the number that exists twice in the array.

You just start from the beginning, keep a hash or something of numbers you've already seen, when you get to a number that appears twice just stop.

worst cat scenario: you see all the n/2 distinct numbers first, and then the next number is a repeat.... n/2+2 (because the number you're looking for isn't part of the n/2 unique numbers)

Read the part about O(1) space complexity too late, but anyway, here is my solution:

#include <iterator>
#include <unordered_set>

template <typename ForwardIterator>
ForwardIterator find_repeated_element(ForwardIterator begin, ForwardIterator end)
{
    typedef typename std::iterator_traits<ForwardIterator>::value_type value_type;
    std::unordered_set<value_type> visited_elements;
    for (; begin != end; ++begin)
    {
        bool could_insert = visited_elements.insert(*begin).second;
        if (!could_insert) return begin;
    }
    return end;
}

#include <iostream>

int main()
{
    int test[] = {8, 10, 3, 4, 1, 1, 1, 1};
    int* end = test + sizeof test / sizeof *test;
    int* p = find_repeated_element(test, end);
    if (p == end)
    {
        std::cout << "the was no repeated element\n";
    }
    else
    {
        std::cout << "repeated element: " << *p << "\n";
    }
}

Due to Pigeon hole principle, you only need to test the first n/2+1 members of the array since the repeated number for certain will be repeated at least twice. Loop through each member, using a hash table to keep track, and stop when there is a member that is repeated twice.

Another solution for O(n) (but not exactly n/2+1), but with O(1) space:

Because you have n/2 of that number, then if you look at it as a sorted array, there are to scenarios for its position:

Either it's the lowest number, so it will take positions 1-n/2 .. or it's not, and then for sure it's in position n/2+1 .

So, you can use a selection algorithm, and retrieve 4 elements: the range [(n/2-1),(n/2+1)] in size
We want then number k in size, so that's ok with the algorithm.

Then the repeated number has to be at least twice in those 4 numbers (simple check)

So total complexity: 4*O(n) + O(1) = O(n)

Regarding complexity O(n/2+1) and space complexity O(1) you can (almost) meet the requirements with this approach:

Compare tuples:

a[x] == a[x+1], a[x+2] == a[x+3] ... a[n-1] == a[n]

If no match is found increase step:

a[x] == a[x+2], a[x+1] == a[x+3]

This will in worst case run in O(n/2+2) (but always in O(1) space) when you have an array like this: [8 1 10 1 3 1 4 1]

qsort( ) the array then scan for first repeat.