AND - Editorial

editorial
, , ,
1

Problem Link:

Practice

Contest

Difficulty:

Simple

Pre-requisites:

Binary Notation, Binary AND operation

Problem:

You are given a sequence of N integer numbers A. Calculate the sum of A[i] AND A[j] for all the pairs (i, j) where i < j.

Explanation:

Solution to the sub tasks 1 and 3:

If you take a look at the AND function for all possible pairs of numbers in the sequence - 0,0; 0,1; 1,0; 1,1 - you will notice that AND equals to one only in case both arguments equal to one, otherwise it equals to zero and will not change the answer in any way. Thus, you just have to calculate the number of pairs (i, j) where i < j and both the i-th and the j-th numbers equal to one. Naturally, the answer equals to o * (o - 1) / 2, where o is the number of ones in the sequence.

Solution to the sub task 2:

In this sub task the constraints are designed in such a way that you can just do the brute force among all the pairs (i, j) where i < j and add the value of the i-th number AND the j-th number to the answer. That will do.

Solution to all the sub tasks:

Let’s use the observation that we had in sub task 3, AND of two binary values is a natural number only in case both of them are true. Another observation is that in some exact bit of the result, AND depends only on this bit in its arguments. That gives rise to the following solution: let’s solve the problem bit-by-bit. At first, let’s count the number of nonzero 0-th bits - we will call this number f(0). Then, there are f(0) * (f(0)-1)/2 ways to add 2^0 to the answer. Generally, there will be f(i)*(f(i)-1)/2 ways to add 2^i to the answer, where f(i) is the number of numbers in the sequence that contain 2^i in their binary representation. Therefore, the final formula is the sum of f(i) * f(i-1)/2 * 2^i over all possible values of i. The maximal possible value of i equals to 29 here, as it is a binary logarithm of maximal possible value in the sequence.

Common bugs

Subtask 3: cnt * (cnt-1)/2 will overflow for cnt = 10^5. “long” datatype is 32 bits in C++

Setter’s solution:

Solution to sub tasks 1 and 3 can be found here

Solution to sub tasks 1 and 2 can be found here

Solution to all the subtasks can be found here

Tester’s solution:

Can be found here

20 Likes
2

Why we are multiplying 2^i to the ans for all i = 0 to 29?

2 Likes
3

can somebody tell me
what this means:

“Common bugs
Subtask 3: cnt * (cnt-1)/2 will overflow for cnt = 10^5. “long” datatype is 32 bits in C++”

why does my code not work when i use:
int cnt;
long long int sum = (cnt*(cnt-1)/2);

4

My Code

Can anybody say what’s wrong with the code.

It’s not passing even single test case in codechef but i got correct ans in my custom test cases.

Please help .

5

Can anybody tell me how we will get answer as 9 ? i’m not understanding

6

Why in the solution there is ll

7

thanks for this
Common bugs
Subtask 3: cnt * (cnt-1)/2 will overflow for cnt = 10^5. “long” datatype is 32 bits in C++
may be i will not understand my problem

8

Can someone help shed light as to why I’m getting an NZEC error on my python 3.4 code?

from itertools import combinations as c
length = int(input())
seq = map(int,input().split())
print(sum(a & b for a, b in c(seq,2)))

The code is fairly basic and it works on my IDE, maybe this has something to do with the Input and Output codechef uses?

9

Because we’re solving the problem bit-by-bit. When we are solving the problem for the i-th bit, we have f(i) numbers where this bit is nonzero. Therefore, there will be f(i)*(f(i)-1)/2 pairs where AND in this bit is nonzero, so we should add them. But we also know that the i-th bit corresponds to the i-th power of two, so the number of “good” pairs for the i-th bit should be multiplied by 2^i.

5 Likes
10

What’s the complexity of 3rd solution?

11

a clever Solution to complete subtask 1,2 & 3 for 73 marks… :wink:

http://www.codechef.com/viewsolution/4661244

12

This is because you are not typecasting it. When the calculation is made, it is still int. What you can do is:
int cnt; long long int sum = (long long int) (cnt*(cnt-1)/2);

13

answer for the test case will be:
(1 AND 2) + (1 AND 3) + (1 AND 4) + (1 AND 5) + (2 AND 3) + (2 AND 4) + (2 AND 5) + (3 AND 4) + (3 AND 5) + (4 AND 5).

This is equal to 0 + 1 + 0 + 1 + 2 + 0 + 0 + 0 + 1 + 4 = 9
Note AND here stands for bitwise AND.

1 Like
14

typecasting.

15

Tests are very weak. Here is my solution, which passes: CodeChef: Practical coding for everyone

and it is actually a brute force one, only saving the inner iteration when A[i] is 0.

16

With all my respect, this solution is wrong, it only works for positive integers. Nowhere in the problem statement is given/stated that the input consists of positive integers only.

For the following input:

4
-1 -2 -3 -4

the proposed tester’s solution gives 6442450923 (the one with the Pascal source code uploaded in S3) → TestANDCodeChefNegativeNumbersInput, Pascal - rextester

while the real answer, computed in a brute-force manner, is -21

17

Can anyone please explain me why does brute force gives wrong answer on test case 2,3 and 4?

18

Can somebody pls give a walkthrough to the code for this question. I am having problem in understanding the concept as well as code. Thanks in advance! :grinning:

19

Another way of doing this. Find all active bits and calculate the answer respectively

//package kg.my_algorithms.codechef;

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
        FastReader fr = new FastReader();
        StringBuilder sb = new StringBuilder();
        int n = fr.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++) arr[i] = fr.nextInt();
        int[] map = new int[Integer.toBinaryString(1_000_000_000).length()];
        for(int a: arr){
            int index = 0;
            while(a>0){
                if((a&1)==1) map[index]++;
                index++;
                a = a>>1;
            }
        }
        long answer = 0L;
        for(int a: arr){
            int index = 0;
            while(a>0){
                if((a&1)==1){
                    map[index]--;
                    answer += map[index]*(1L<<index);
                }
                index++;
                a = a>>1;
            }
        }
        sb.append(answer).append("\n");
        output.write(sb.toString());
        output.flush();
    }
}











class FastReader {
    BufferedReader br;
    StringTokenizer st;

    public FastReader()
    {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            }
            catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() { return Integer.parseInt(next()); }

    long nextLong() { return Long.parseLong(next()); }

    double nextDouble()
    {
        return Double.parseDouble(next());
    }

    String nextLine()
    {
        String str = "";
        try {
            if(st.hasMoreTokens()){
                str = st.nextToken("\n");
            }
            else{
                str = br.readLine();
            }
        }
        catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}