3
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\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.