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; }