# HackerRank Manipulative Numbers problem solution

In this HackerRank Manipulative Numbers problem solution we have given A list of N numbers and then find the largest K such that there exists a k-manipulative permutation B.

## Problem solution in Python.

```#!/bin/python3

import os
import sys
import collections

def naive_solver(arr):
for k in range(100):
ctr = collections.Counter([num >> k for num in arr])
print(type(ctr))
for elem in ctr:
if ctr[elem] * 2 > len(arr):
return k-1

def manipulativeNumbers(a):
return naive_solver(a)

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

a_count = int(input())

a = list(map(int, input().rstrip().split()))

result = manipulativeNumbers(a)

fptr.write(str(result) + '\n')

fptr.close()```

## Problem solution in Java.

```import java.util.Arrays;
import java.util.Scanner;

public class Solution
{
int n;
Scanner sc=new Scanner(System.in);
long[] arr;
void kks()
{
n=sc.nextInt();
arr=new long[n];
for(int i=0;i<n;i++)
arr[i]=sc.nextLong();
}
boolean kk(long[] arr)
{
Arrays.sort(arr);
for(int i=0;i<n;)
{
long t=arr[i];
int c=0;
for(;i<n&&arr[i]==t;i++)
c++;
if (c>n/2)
return false;
}
return true;
}
void kkk()
{
for (int k=32;k>=0;k--)
{
long[] temp=new long[n];
for (int j=0;j<n;j++)
temp[j]=arr[j]>>k;
if (kk(temp))
{
System.out.println(k);
return;
}
}
System.out.println("-1");
}

public static void main(String[] args)
{
Solution ob=new Solution();
ob.kks();
ob.kkk();
}
}```

## Problem solution in C++.

```/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <stdint.h>
#include <stdio.h>

#include <algorithm>
#include <map>
#include <vector>

using namespace std;

const int32_t N = 101;
int32_t A[N];
int32_t n;

bool Ok(int32_t k) {
map<int32_t, int32_t> M;
for (int32_t i = 30; i >= k; i--) {
}
for (int32_t i = 0; i < n; i++) {
}
vector<int32_t> vec;
for (map<int32_t, int32_t>::iterator it = M.begin(); it != M.end(); ++it) {
vec.push_back(it->second);
}
sort(vec.begin(), vec.end());
if (vec.size() == 1) return false;
int32_t s = vec[0];
for (int32_t i = 1; i < vec.size(); i++) {
if (s < vec[i]) return false;
s += vec[i];
}
return true;
}
int32_t main() {
scanf("%d", &n);
for (int32_t i = 0; i < n; i++) {
scanf("%d", &A[i]);
}
for (int32_t k = 30; k >= 0; k--) {
if (Ok(k)) {
printf("%d\n", k);
break;
}
}
return 0;
}```

## Problem solution 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;
}

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]);

qsort (A,n,sizeof(int),compare);

for(i=31;i>=1;i--)
{
memcpy(&B,A,n* sizeof(int));

for(j=0;j<n;j++)
B[j]=B[j]>>i;

if(printMajority(B,n)==0)
{
printf("%d\n",i);
flag=0;
break;
}
}
if(flag==-1)
printf("-1\n");
return 0;
}```