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\$
1
  • \$\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
    Commented Feb 18, 2016 at 9:55

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.