PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Hasan Jaddouh
Tester: Joud Zouzou
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy
PREREQUISITES:
Observations, bitwise operations and being greedy once again
PROBLEM:
Given an array A with N elements, we need to find the minimum value of \sum A_i \oplus X by choosing any value for X.
QUICK EXPLANATION
- Writing all elements of A_i in binary, Consider each bit separately. Count the number of elements having the current bit set.
- If there are p elements with bit x set, current bit contributes p*2^x to the total sum which we need to minimize.
- If p > N-p, we can choose to set the current bit of X on so that p on bits become off bits and N-p off bits become set bits, reducing answer by (p- (N-p))*2^x.
EXPLANATION
Quick explanation nearly explained it all.
In XOR operation, the current bit is independent of the result of XOR operation on lower bits, which allows us to solve this problem separately for each bit and simply add the answers.
W repeat the process for each bit. For bit x, if there are p elements with the current bit on, we get the sum as p*2^x.
In XOR operation, we can choose to leave the current bits as it is by setting the current bit of X as off or flip all of them by setting the current bit of X as on. If we keep it off, the current bit contributes p*2^x to answer. If we keep it on, the current bit contribute (N-p)*2^x to answer. In order to minimize sum, we can simply add min(p*2^x, (N-p)*2^x) to answer for the current bit.
So, minimum sum is \sum_{i =0}^{B-1} min(p_x, N-p_x)*2^i if there are p_x elements with ith bit set in array A and B is the number of bits.
TIME COMPLEXITY
The time complexity is O(N*B) per test case where B is the number of bits.
SOLUTIONS:
Setter's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int T;
int n;
int arr[100100];
int sm_n=0;
int main(){
//freopen("01.txt","r",stdin);
//freopen("01o.txt","w",stdout);
T=readIntLn(1,1000);
while(T--){
n=readIntLn(1,100000);
sm_n+=n;
assert(sm_n<=1000000);
for(int i=0;i<n;i++){
if(i==n-1){
arr[i]=readIntLn(1,1000000000);
} else {
arr[i]=readIntSp(1,1000000000);
}
}
for(int i=0;i<30;i++){
int cnt = 0;
for(int j=0;j<n;j++){
if(arr[j] & (1<<i)){
cnt++;
}
}
if( cnt < n - cnt){
continue;
}
for(int j=0;j<n;j++){
arr[j] ^= 1<<i;
}
}
long long sol=0;
for(int i=0;i<n;i++){
sol += arr[i];
}
cout<<sol<<endl;
}
assert(getchar()==-1);
}
Tester's Solution
// Full Solution
#include <bits/stdc++.h>
using namespace std;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
long long a[1000005];
long long num[1000];
int main()
{
int t = readIntLn(1,1000);
while(t--)
{
int n = readIntLn(1,100000);
for (int i=0;i<=50;i++)num[i]=0;
for (int i=1;i<=n;i++)
{
if (i<n)
a[i]=readIntSp(1,1000000000);
else
a[i]=readIntLn(1,1000000000);
for (int j=0;j<=30;j++)
{
if ((1<<j)&a[i])num[j]++;
}
}
long long ret=0;
for (int i=0;i<=30;i++)
{
long long cur = min(num[i],n-num[i]);
ret+=(((1LL)<<i)*cur);
}
cout<<ret<<endl;
}
assert(getchar()==-1);
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
//Solution Credits: Taranpreet Singh
public class Main{
//SOLUTION BEGIN
//This code is not meant for understanding, proceed with caution
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni(), B = 30;
int[] s = new int[B];
for(int i = 0; i< n; i++){
int x = ni();
for(int b = 0; b< B; b++)if(((x>>b)&1)==1)s[b]++;
}
long ans = 0;
for(int b = 0; b< B; b++)ans+= (1l<<b)*Math.min(s[b], n-s[b]);
pn(ans);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
long mod = (long)1e9+7, IINF = (long)1e18;
final int INF = (int)1e9, MX = (int)1e6+1;
DecimalFormat df = new DecimalFormat("0.0000000");
double PI = 3.1415926535897932384626433832792884197169399375105820974944, eps = 1e-8;
static boolean multipleTC = true, memory = false;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
int T = (multipleTC)?ni():1;
// Solution Credits: Taranpreet Singh
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
else new Main().run();
}
long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to Share your approach, If it differs. Suggestions are always welcomed.