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;


                if(topic[i][k] == '1'  || topic[j][k] == '1'){


            if(sub > maxSubjects){


            if(sub == maxSubjects){


    return 0;
  • \$\begingroup\$ 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. \$\endgroup\$ – nwp Feb 18 '16 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.