CODEWITHSUNDEEP
algorithmdata-structures
user11067275
user11067275

Reputation: 99

Reducing time complexity from n^2

There are n students in a class. Soon, there's going to be an inter-school science quiz, where there'll be questions on 4 subjects, call them 1,2,3 and 4 for simplicity. There should 2 students in a team. Any student is equally likely to be good or bad at a particular subject.

We are given as input n rows, each with 4 entries in it. The student is good at i-th subject if the i-th column is equal to 1. I'm supposed to find out the total number of ways in which the school can send a team so that the two students together know all the 4 subjects.

For example, 

S1: 1 1 1 1
S2: 1 1 0 1
S3: 1 0 1 1
S4: 0 0 1 1
S5: 0 0 0 0

Student 1 can go with any student since all the subjects are his strength. => 4

Student 2 can go with S3 and S4, since S2 is good in subject 1,2 and 4 and S3 and S4 are good in subject 3. => 2 (Note that (S1,S2) was already counted)

S3 will go with the one good at subject 2=> none

S4: Similarly, none.

Hence, ans=4+2=6

My solution:-

ans=0;
//arr is the array containing subject-wise "strength" of students
for(int i=0;i<n;i++){
    ArrayList<Integer> a=new ArrayList<>();
    for(int j=0;j<4;j++)
        if(arr[i][j]==0)
            a.add(j);
    if(a.size()==0)
        ans+=n-i-1;
    else
        for(int j=i+1;j<n;j++){
            bool=false;
            for(int k=0;k<a.size();k++){
                if(arr[j][a.get(k)]==0)
                    break;
                bool=true;
            }
            if(bool)
                ans++;
        }
}
System.out.println(ans);

Now I know my solution is correct, but its time complexity is O(n^2), and I'm looking for a better solution for the same. Thanks!

Upvotes: 3

Views: 4686

Answers (1)

Prune
Prune

Reputation: 77850

You can reduce the complexity on number of students by spending memory for the combinations of subjects.

Build a list of 2^s elements, where s is the quantity of subjects. Index the list by the combinations of subjects, interpreted as a binary number. For instance, S2 has a value of 13, and is missing a value of 2.

First tally the "needs" that each student can fill. For each combination of 1 bits in the student's known subjects, increment that index of the tally list.

for student in student_list:

    score =   # student's covered subjects as an int

    tally = [0]*16
    for idx in range(16):
        if idx & score == idx:
            tally[idx] += 1

You now have a list of how many students can cover each combination of needed subjects. This is O(n * 2^s)

For each student, find the needed score, the 1's complement of the student score. It is now a simple matter to add all of the tallies for the needed scores.

team_ct = 0

for student in student_list:

    needed =   # student's needed subjects as an int; this is 15-score (above)
    team_ct += tally[needed]

Now, every pairing has been counted twice, so divide team_ct by 2. Yes, this last bit of code can be dropped into a one-liner:

team_ct = sum([tally[15-score] for score in foo]) / 2

Where foo is a construct of all student scores. This part is O(n).

Upvotes: 4

Related Questions