Samsung Interview Question
Software EngineersCountry: India
Interview Type: Written Test
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++){
cin>>arr[i];
}
sort(arr,arr+n);
long long answer=0;
for(int bit=0;bit<32;bit++){//taking contribution from bit
for(int i=0;i<n;i++){
//i th element is minimmum
for(int j=i+1;j<n;j++){
long long val=((1<<bit)&arr[i]);
long long val2=((1<<bit)&arr[j]);
if(val==0 && val2==0){
continue;
}
int countInBetweenElements=j-i-1;
long long temp=((pow(2,countInBetweenElements))*(pow(2,bit)));
answer+=temp;
}//mtlb jith element max lelia to bich walo se kitni trh k contibution aaenge
//i and j ka OR aaega power(2,countInBetweenElements)-1 subsets me
}
}
cout<<answer<<endl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main(){
int s;
cin>>s;
int arr[s];
for(int i=0;i<s;i++) cin>>arr[i];
sort(arr, arr+s);
int ans = 0;
for(int i=0;i<s-1;i++){
int a = arr[i];
for(int j=i+1;j<s;j++){
int b = arr[j];
int k =a|b;
k*=pow(2, j-i-1);
ans+=k;
}
}
cout<<ans;
return 0;
}
the maximum is obviously the set it self so 1|2|3 in above case (=1|3=2|3}, the smallest seem to be the smallest|2nd smallest. O(n) algo, find the smallest, 2nd smallest and or all elements... or and sum. done.
- Chris May 23, 2018