I was doing a programming question in C++ at HackerRank. Given a set of up to 500 bitstrings, each up to 500 bits long, the task is to find the pair a and b such that the bitwise OR contains the most 1s.
I solved the question with Time Complexity of O(n3). I can't figure out how i can solve the question with a better time complexity. I looked at Problem-Settlers Code but it was again of the order of O(n3).
#include <math.h>
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n;
int m;
cin >> n >> m;
vector<string> topic(n);
for(int topic_i = 0;topic_i < n;topic_i++){
cin >> topic[topic_i];
}
int maxSubjects=0, maxTeams=0;
for(int i=0;i<n;i++){
for(int j=(i+1);j<n;j++){
int k=0,sub=0,max=0;
while(k<m){
if(topic[i][k] == '1' || topic[j][k] == '1'){
sub++;
}
k++;
}
if(sub > maxSubjects){
maxSubjects=sub;
maxTeams=0;
maxTeams++;
continue;
}
if(sub == maxSubjects){
maxTeams++;
}
}
}
cout<<maxSubjects<<endl;
cout<<maxTeams<<endl;
return 0;
}
std::bitset
, not aschar
s.bitset
has operators to perform bitwise or, so you can do that instead of your inner loop. If you turn on optimization you have a decent chance of the compiler vectorizing the operation so you change 64 bits at a time when usingbitset::operator |
. I don't have a good idea how to reduce complexity either. \$\endgroup\$