Good Pairs CodeChef Solution

Problem – Good Pairs CodeChef Solution

You are given N integers: A₁, A₂, …, A_N. You need to count the number of pairs of indices (i, j) such that 1 ≤ i < j ≤ N and A_i | A_j ≤ max(A_i, A_j).

Note: A_i | A_j refers to bitwise OR.

Input

• The first line of the input contains an integer T, denoting the number of test cases. The description of each testcase follows.
• The first line of each testcase contains a single integer: N
• The second line of each testcase contains N integers: A₁, A₂, …, A_N.

Output

For each test case, output a single line containing the answer for that test case.

Constraints

• 1 ≤ T ≤ 20
• 1 ≤ N ≤ 10⁶
• 0 ≤ A_i ≤ 10⁶
• 1 ≤ Sum of N over all test cases ≤ 10⁶

Subtasks

Subtask #1 (20 points):

• 1 ≤ N ≤ 10³

Subtask #2 (80 points):

• Original constraints

Sample 1:

Input:
1
3
1 2 3
Output:
2

Explanation:

There are three possible pairs of indices which satisfy 1 ? i < j ? N: (1, 2), (1, 3) and (2, 3). Let us see which of those satisfy A_i | A_j ? max(A_i, A_j):

• (1, 2): A₁ | A₂ = 1 | 2 = (01)₂ | (10)₂ = (11)₂ = 3. But max(A₁, A₂) = max(1, 2) = 2, and 3 ? 2 is not correct. Hence this is not a valid pair.
• (1, 3): A₁ | A₃ = 1 | 3 = (01)₂ | (11)₂ = (11)₂ = 3. And max(A₁, A₃) = max(1, 3) = 3, and 3 ? 3 is correct. Hence this is a valid pair.
• (2, 3): A₂ | A₃ = 2 | 3 = (10)₂ | (11)₂ = (11)₂ = 3. And max(A₂, A₃) = max(2, 3) = 3, and 3 ? 3 is correct. Hence this is a valid pair.

So there are a total of 2 valid pairs, and hence the answer is 2.

Good Pairs CodeChef Solution in Pyth 3

for _ in range(int(input())):
    n = int(input())
    arr = list(map(int, input().strip().split()))
    d = {}
    for i in range(n):
        if arr[i] not in d:
            d[arr[i]] = 1
        else:
            d[arr[i]] += 1
    ans = 0
    for A1 in d.keys():
        ans += d[A1] * (d[A1] - 1)
        for A2 in d.keys():
            if A1 != A2 and (A1 | A2) <= max(A1, A2):
                ans += d[A1] * d[A2]
    print(ans // 2)

Good Pairs CodeChef Solution in C++14

#include<bits/stdc++.h>
#include<ostream>
using namespace std;

#define int long long
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
const int INF = numeric_limits<int>::max();
const int nax = (int)(3000901);
const int mod = 1e9 + 7;

template<class X, class Y>
bool maximize(X& x, const Y y) {
    if (y > x) {x = y; return true;}
    return false;
}
template<class X, class Y>
bool minimize(X& x, const Y y) {
    if (y < x) {x = y; return true;}
    return false;
}

int arr[nax], dulpet[nax];
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        memset(dulpet, 0, sizeof dulpet);
        for (int i = 1; i <= n; ++i) {
            cin >> arr[i];
            dulpet[arr[i]]++;
        }
        int ans = 0;
        for (int mask = 0; mask < (1 << 20); ++mask) {
            ans -= (dulpet[mask] - 1) * dulpet[mask] / 2;
        }
        for (int i = 0; i < 20; ++i) {
            for (int mask = 0; mask < (1 << 20); ++mask) {
                if (mask & (1 << i)) {
                    dulpet[mask] += dulpet[mask ^ (1 << i)];
                }
            }
        }
        for (int i = 1; i <= n; ++i) {
            ans += dulpet[arr[i]] - 1;
        }
        cout << ans << '\n';
    }
    return 0;
}

Good Pairs CodeChef Solution Review:

In our experience, we suggest you solve this Good Pairs CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Good Pairs CodeChef Solution

Find on CodeChef

Conclusion:

I hope this Good Pairs CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions