Manipulative Numbers

                            Solution in C :

In  C :






#include<stdio.h>
#include<string.h>
int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}
int isMajority(int a[], int size, int cand)
{
    int i, count = 0;
    for (i = 0; i < size; i++)
      if(a[i] == cand)
         count++;
    if (count > size/2)
       return 1;
    else
       return 0;
}

int findCandidate(int a[], int size)
{
    int maj_index = 0, count = 1;
    int i;
    for(i = 1; i < size; i++)
    {
        if(a[maj_index] == a[i])
            count++;
        else
            count--;
        if(count == 0)
        {
            maj_index = i;
            count = 1;
        }
    }
    return a[maj_index];
}
  
int printMajority(int a[], int size)
{
  int cand = findCandidate(a, size);
  if(isMajority(a, size, cand))
    return -1;
  return 0;
}

/*void print(int *A,int n)
{
  int i;
  for(i=0;i<n;i++)
    printf("%d ",A[i]);
  printf("\n");
}*/
int main()
{
  int n,A[1000],i,j,B[1000],flag=-1;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%d",&A[i]);
  //print(A,n);
  qsort (A,n,sizeof(int),compare);
  //print(A,n);
  for(i=31;i>=1;i--)
  {
    memcpy(&B,A,n* sizeof(int));
    //print(B,n);
    for(j=0;j<n;j++)
      B[j]=B[j]>>i;
    //print(B,n);
    if(printMajority(B,n)==0)
    {
      printf("%d\n",i);
      flag=0;
      break;
    }
  }
  if(flag==-1)
      printf("-1\n");
  return 0;
}
                        

                        Solution in C++ :

In  C ++  :







#include <iostream>
#include <algorithm>
using namespace std;

int highbit(int x)
{
    int k = -1;
    while (x != 0)
    {
        x >>= 1;
        k++;
    }
    return k;
}

int main()
{
    int a[100], b[100], n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int *p = a, *q = b;
    int m = n / 2;
    sort(p, p + n);
    int k = highbit(p[m]);
    while (k >= 0)
    {
        int x = 1 << k;
        for (int i = 0; i < n; i++)
            q[i] = p[i] ^ x;
        sort(q, q + n);
        int s = highbit(q[m]);
        if (s == k) break;
        swap(p, q);
        k = s;
    }
    cout << k << endl;
    return 0;
}
                    

                        Solution in Java :

In  Java :







import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;

public class Solution {
	static InputStream is;
	static PrintWriter out;
	static String INPUT = "";
	
	static void solve()
	{
		int n = ni();
		int[] a = new int[n];
		int[] b = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		
		for(int k = 30;k >= 0;k--){
			for(int i = 0;i < n;i++)b[i] = a[i] >>> k;
			if(iskmul(b)){
				out.println(k);
				return;
			}
		}
		out.println(-1);
	}
	
	static boolean iskmul(int[] a)
	{
		int n = a.length;
		Arrays.sort(a);
		int ct = 0;
		int max = 1;
		for(int i = 0;i < n;i++){
			if(i == 0 || a[i] != a[i-1]){
				ct = 1;
			}else{
				ct++;
				max = Math.max(max, ct);
			}
		}
		return max <= n/2;
	}
	
	public static void main(String[] args) throws Exception
	{
		long S = System.currentTimeMillis();
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		solve();
		out.flush();
		long G = System.currentTimeMillis();
		tr(G-S+"ms");
	}
	
	static boolean eof()
	{
		try {
			is.mark(1000);
			int b;
			while((b = is.read()) != -1 && !(b >= 33 && b <= 126));
			is.reset();
			return b == -1;
		} catch (IOException e) {
			return true;
		}
	}
		
	static int ni()
	{
		try {
			int num = 0;
			boolean minus = false;
			while((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'));
			if(num == '-'){
				num = 0;
				minus = true;
			}else{
				num -= '0';
			}
			
			while(true){
				int b = is.read();
				if(b >= '0' && b <= '9'){
					num = num * 10 + (b - '0');
				}else{
					return minus ? -num : num;
				}
			}
		} catch (IOException e) {
		}
		return -1;
	}
	
	static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
                    

                        Solution in Python : 
                            
In  Python3 :






from collections import Counter
input()
a = list(map(int, input().split()))
answer = -1
for i in range(32):
    if Counter(x >> i for x in a).most_common(1)[0][1] <= len(a) // 2:
        answer = i
    else:
        break
print(answer)