CareerCup

The key point that makes O(1) time& space possible is that the array is sorted.

The idea is, if the element that repeated >n/2 time (half-major element), they must be next to each other in the array. And they must cross some "land-mark", that is the middle of the array.

So, checking the middle element A[n/2], comparing it with A[0] and/or A[n] can tell whether it's major element. EDITED: A[n/2] must be the answer given if half-majority exists.

For the case of majority > n/4 (quarter-majority): Same idea, however we need more "land-marks". I believe checking position k*n/8 for k = 0..8 will sufficient to check for the majority element.

For the case array is NOT sorted, I think O(1) time is not possible. However, O(n) time, O(1) space algorithm exists. Check this post about majority elements: capacode. com/array/major-element-in-array/ Thanks!

EDITED for the case n/4-majority:
- Check if there is a repeated segment S crosses at least 2 landmarks.
- If S crosses 3 landmarks or more: length of S must be >n/4, found S, done.
- If S crosses only 2 landmarks u and u+1:
Reduce the problem into the case "half-majority" with array from landmark u-1 to landmark u+2.

Since the array is sorted, and we have a guarantee that such an element exists, then the answer is always

input[Math.ceil(n/2)]

Examples: (Realize that the repeated element always takes up >= n/2 elements.)
Input: {1,2,3,3,3,3,3,3,4,5,6}
Input: {3,3,3,3,3,3,4,5,6,7,8}
Input: {1,2,3,4,5,6,6,6,6,6,6}

Ceil(n/2) = Ceil(11/2) = 6
input[6-1] = repeated elements in all cases. There are some edge cases depending on the array length (0, 1, 2)

I'll update with the n/4 solution.

# Given a sorted array of size N of int32, find an element that repeats > ceil(N / 2) times. #Your algo may assume that there will be always such element. Space/time O(1). 
# Follow up question: Now element repeats > ceil(N / 4) times. Space/time O(1)

def find_repeat(a):
    b = len(a)
    print(b)
    if((a[int(b/4)] == a[int(b/2)])or(a[int(b/2)] == a[int(3*b/4)-1])
       or(a[int(3*b/4)-1] == a[b-1])):
        return 1
    else:
        return 0
    
        
#x = [1,1,1,1,2,2,2,3,3]
x = [1,2,3,4,5,6,7,89]
if(find_repeat(x) == 1):
    print("Yes")
else:
    print("No")

For first, it's the middle element.

For second, it's a bit trickier. Suppose we have splitted the array into 8 portion, the the array will looks like this,

(start element)1----2----3----4----5----6----7----8(end element)

If any of the alternate position's element matches with each other then it definitely has that element. We need atmost six comparison to determine the exact element.
[1---- to ----3] or,
[2------4] or,
[3------5] or
[4------6] or
[5------7] or
Since the array must have the element, then it must be any element from [6 --- to --- 8] range.

In O(n) time/space , try to transform the array in this form x, a, x, b, x, c, x, ... when 'x' will be the element that you want.
BTW: I think you need to see all the elements so the time at least is O(n)

Are we sure this is O(1) time? The Misra-Gries algorithm that is generally used to solve this problem is O(n) time and O(1) space.

This is indeed a O(1) problem. Note the key is that the array is already sorted. So if an element repeats ceiling(N/2) times in the array, then no matter it is placed, the center element will be that element. If number of element is even so there is no precise center, then exam if the center two elements are the same or not. If they are not the same, pick up one more element on either side to compare. The element that has an identical peer is the answer.

I think he is asking to find the Majority Element

Could we do in the following way . First check ceil(n/2)-1 element if it is majorant more than ceil(n/2) repeats.If is such then we return. Otherwise we split array in two halves and check in both if ceil(m/2)-1 is majorant where m should be n/2.

For the N/2 case, the center element is definitely the answer.
For the N/4 case, divide the array into 8 equal pieces, we have 6 marking points plus start and end of the array. The repeating element is the one which repeats at least 3 times in any of these 8 marking points (definitely the repeats will be in sequential order) like

public int findRepN4(int[] arr)
{
	if(arr==null)
	{
		throw new NullPointerException();
	}
	int mid=(arr.length-1)/2;
	int idx=-1;
	idx=getRep(0,mid,arr);
	if(arr.length%2==0)
	{
		return(idx!=-1)?arr[idx]:arr[checkSub(mid+1,end,arr)];
	
	}
	return arr[checkSub(mid,end,arr)];
}
	







private int checkSub(int start,int end,int[] arr)
{
	int mid=end+start/2;
	if(end-start+1%2==0)
	{
		if(arr[mid]==arr[start])
		{
			return start;
		}
		return(arr[end]==arr[mid+1]?end:-1);
	}
	return(arr[mid]==arr[start]||arr[end]==arr[mid])?mid:-1;	
	
}

void findRepeatEleN4(int arr[N])
{
	int i = ceil(N/4);
	cout << "\n repeated elements are";
	for(int j=0;j<N;j++)
	{
		if(arr[j] == arr[j+i])
		{
			cout << arr[j];
			j=j+i;
		}
	}
}

you can solve it in O(n) time and constant space using Fast Majority algorithm. Read this algorithm.

why did u assume continuous repitition??

def findRepeatCeilHalf( sorted_array ):    
    return sorted_array[len(sorted_array) // 2]

def findRepeatCeilQuarter( sorted_array ):   
    
    if len(sorted_array) < 5:
        return sorted_array[0]

    step_size = int(np.ceil(len(sorted_array) / 4.0) // 2)
    termination_crit = int(np.ceil(np.ceil(len(sorted_array) / 4.0) / step_size))
    
    cons_val = sorted_array[0]
    cons_ct = 1
    pos = step_size
    
    while True:
        curr_pos = min(pos, len(sorted_array) - 1)
        curr_val = sorted_array[curr_pos]
        if (curr_val == cons_val):
            cons_ct += 1
            if cons_ct >= termination_crit:
                return curr_val
        else:
            cons_val = curr_val
            cons_ct = 1            
            
        if curr_pos == len(sorted_array) - 1:
            #this should never happen
            break
        
        pos += step_size
    
    return ""

return middle