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;
    int32_t mask = 0;
    for (int32_t i = 30; i >= k; i--) {
        mask |= (1<<i);
    }
    for (int32_t i = 0; i < n; i++) {
        M[A[i]&mask]++;
    }
    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("%dn", 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("%dn",i);
      flag=0;
      break;
    }
  }
  if(flag==-1)
      printf("-1n");
  return 0;
}