CareerCup

Idea is similar to finding majority element in an array.

Let 'x' be the element present 'n' times in the array.
We'll compare 2 consecutive array indices at a time e.g 0,1 2,3 4,5 and so on.
If any of these comparisons finds two matching numbers, then that is our answer.

However there is a corner case where 'x' is present alternately
e.g. x1x2x3x4x5x6x7x8x9xA....
In this case, at the end of 'n' comparisons(see above step), we won't be finding any match. Now, if we compare the last four elements, we are guaranteed to find two x's.
We don't need to scan the whole array as wenlei.zhouwl mentioned.

O(n) solution. Use a hash map to insert the n elements. The number with the first insert failure is the number that is redundant.

Method 1. Hash. Time:O(N), Space: O(N).
Method 2. Let A be the array and N be the size.
2a: Compare 1st and 3rd element if matched return the number.
2b: Compare 2nd and 4th element if matched return the number.
2c: for i=1 to N, if(A[i-1]==A[i]) return A[i].
Time: O(N), Space: O(1).

in any case : two same numbers will be adjacent to each other.
just check with previous number....
except in one case : in which all numbers will be alternate..(check a[0] == a[2])

The solutions here (although correct) seems quite trivial. We have additional information here (n repeating elements out of 2n elements) that we are not making use of...Not sure but I feel there may be a better solution to this...Still thinking..

How about below:

1. group numbers in 3-element set
2. check if two is same for any of the set

n = 2 (say, "ab") and 4 (say, "abca") are special cases, for which we need manual testing.

Sort the 2n number ( O(nlogn) ). Look at the middle number. This is the repeating number.

Since there are n all different numbers and n same numbers, for example, x. Number x must be either beside another x or one element away. So comparing data[i] with data[i+1] and data[i+2] would be able to figure out. Complexity is O(n).

Is this not a majority algorithm problem???
are you sure an element is repeated n times (or n+1 times)???

can someone explain me how majority algorithm works and what is the significance of "more than n/2 similar element" in majority element question....thanks in advance

In any algorithm the worst case is always O(N).
we can work like this also
take 4 Pivot
@ index 0 index n/2 index n index 3n/2.
compare the value at each index with each other. match found return the element.
else increase the each index by 1 and do the same operation.

Guys Wat about Binary Search Tree implementation for this solution ..I think BST should be good wat to find...

Compare (1st,3rd), (2nd,4th) and then all elements with its next element.
whenever a match happens, return that element.

ok..here is my take.
1. Take any number from array , lets say first one and check of it repeats n/2 times. If yes, you are done otherwise perform step 2.
2. Apply majority element algorithm(>n/2 repeat condition), ignoring the element considered in 1st step. (since n is reduced by one, the element which was just 'n/2' times earlier now becomes majority)

Cheers..

Here's O(n) working solution
1. Declare two variables a) count variable to keep track of count of majority element.
2. Majority element.
3. Do a for loop and repeat following steps 4-6 until end of array is reached.
4. if current array element equals majority element, increment count
5. else, if count is 0, update majority element with current array element and increment count.
6. else if count is not 0 then decrement count.
7. Do another for loop and count the number of occurrences of majority element in the array, if it's half the array size then we have found the majority element, else there's no majority element.

Time complexity - O(n)
Space complexity - O(1)

A O(n) solution, assuming n is the length of array:
1. Use Linear time selection to get n/2th and n/2+1th element, one of these two element is what we want.
2. Check which one appear n times in array.

#include <stdio.h>
#include<iostream>

using namespace std;

int findnby2elements(int arr[],int len) {
if(!arr)
return -1;
int ele=arr[0],count=1;
for(int i = 0; i<len;i++) {
if(arr[i]==ele)
count++;
else count--;
if(count<0)
ele=arr[i];
}
count=0;
for(int i = 0; i<len;i++) {
if(arr[i]==ele)
count++;
}
if(count==(len/2))
return ele;
else return -1;
}

int main(void) {
int arr[] = {1};
cout<<findnby2elements(arr,1);
getchar();
}

So the group-by-3 method works well, but its worst case number of comparisons needed is about 3n/2 (just consider the case where each of the first n/2 3-groups are formed from 2 non-majority elements and 1 majority element, and there are worst case 3 comparisons per such group). Let's see if we can get the number of comparisons down to around n. Pair off 2n-4 of the elements. At worst each pair has one majority and one non-majority element for a total of (2n-4)/2 = n-2 comparisons. For the remaining 4 elements pick a group of 3. If they are all different, the 4th is majority. If two are the same we are also done. Either case takes 3 comps for a worst case total of n+1 comparisons. Indeed, n+1 is minimal worst case number because if n comps sufficed it must mean that we can divide the 2n elements into disjoint pairs and guarantee finding the majority. But it's not possible to guarantee that we won't get all pairs having one majority and one non-majority. Thus n+1 is minimal number of comparisons possible.

There is a simple expected constant time randomized algorithm. Simply select two distinct elements int he array say a_i and a_j. If a_i = a_j, then we have found our repeated element. Repeat until we find i and j such that a_i = a_j.

It is easy to show that a_i = a_j with probability greater than 1/6 (assuming n is say at least 10). Hence after only an expected constant number of trials we will found our repeated element with probability say > 99.99999%

How about this ...

Take the last element and search how many time occurs if count is n then return this number
if not

then we have 2n-1 element where one number is repeating n times so we can find majority element in O(n) time

Traverse the array, every time remove two different elements. O(n).
So at last there will be two situations:
1. several elements are left and they have the same value. So this value is what we want. O(1)
2. two elements are left: one element which occurs n / 2, one other element. In this situation, we just need to traverse the array, and count the number occurs of the remaining element. O(n)

Here is the code:

#include <iostream>

using namespace std;

int find(int *array, int n)
{
    int one = array[0];
    int num = 1;
    for (int i = 1; i + 1 < n; ++i)
    {
        if (num == 0)
        {
            one = array[i];
            num = 1;
        }
        else
        {
            if (one == array[i])
            {
                ++num;
            }
            else
            {
                --num;
            }
        }
    }
    if (num > 1)
    {
        return one;
    }
    else if (array[n - 1] == one)
    {
        return one;
    }
    else
    {
        int num = 0;
        for (int i = 0; i < n; ++i)
        {
            if (array[i] == one)
            {
                ++num;
            }
        }
        if (num == n / 2)
        {
            return one;
        }
        else
        {
            return array[n - 1];
        }
    }
}

int main()
{
    int n;
    int array[1000];
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> array[i];
    }
    int result = find(array, n);
    cout << result << endl;
    return 0;
}

Try in 2 steps:
1. Return if any two consecutive number are same.
2. if Pass 1 fails, they have two be alternative positions

int SameVal(int a[], int size) {
  for (int i=1; i<size;i++) {
    if (a[i] == a[i-1]) return a[i];
  }

  if (a[0] == a[2]) return a[0];
  
  return a[1];
}

How about this?
Compare first three elements
if any two of them are same then return that element.
if all three are different then
we can remove that 3 elements and pass the left over array to find majority element in O(n)

Here is my solution ...

consider this simple function first

bool CheckIfMoreThanHalf(int[] arr, int x) which returns true if this number is more than Half times in an array.

Now here is my solution

int GetMajorityElement(int[] arr)
{
if (CheckIfMoreThanHalf(arr, arr[0]) return arr[0];
int maxInt = arr[1];
int maxIntCount = 1;
for (int idx = 2; idx < arr.Length; idx++)
{
if (maxIntCount == 0) { maxInt = arr[idx]; maxIntCount= 1}
else if (arr[idx] == maxInt) maxIntCount++;
else maxIntCount--;
}
if (CheckIfMoreThanHalf(arr, maxInt)) return maxInt;
return -1; // or whatever error value.
}

It will give you the correct element. No need of sorting and all.

int findCandidate(int arr[],int n)
{
	int maj_ele=0,count=1;
	for(int i=1;i<n;i++)
	{
		if(arr[maj_ele]==arr[i])
			count++;
		else
			count--;
		if(count==0)
		{
			maj_ele=i;
			count=1;
		}
	}
	return arr[maj_ele];
}