# ACM-ICPC HackerRank challenge in C++

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

• You mean O(n²) in the number of bitstrings and O(n^3) in the number of bits, right? I would store the bits as bits, with an std::bitset, not as chars. 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 using bitset::operator |. I don't have a good idea how to reduce complexity either. – nwp Feb 18 '16 at 9:55