Help In understanding this particular problem ( link in the post )

help
1

Can someone please help me understand this problem, I’m not able to understand what a variable k in this problem means,
Solve This | CodeChef

2

The Problem is fairly basic. k represents the number of Non-negative Integers i less than or equal to a given Integer N, whose sum is equal to the bit-wise xor of N\ and\ i.

K = |\ \{\ i\mid\ i+N = i\ \oplus\ N,\ 0\le i\le N\}\ | where \oplus represents bit-wise XOR operation.

Few examples follow:

  1. For N = 1: K = 1, where i \isin\ \{0\}:
    0+1 = 0\oplus 1

  2. For N = 2: K = 2, where i \isin \{0,1\}:
    0+2 = 0\oplus 2,\ 1+2 = 1\oplus 2

  3. For N = 3: K = 1, where i \isin \{0\}:
    0+3 = 0\oplus 3

  4. For N = 4: K = 4, where i \isin \{0,1,2,3\}:
    0+4 = 0\oplus 4,\ 1+4 = 1\oplus 4,\ 2+4 = 2\oplus 4,\ 3+4 = 3\oplus 4

  5. For N = 5: K = 2, where i \isin \{0,2\}:
    0+5 = 0\oplus 5,\ 2+5 = 2\oplus 5

  6. For N = 6: K = 2, where i \isin \{0,1\}:
    0+6 = 0\oplus 6,\ 1+6 = 1\oplus 6
    So on.

Now, the maximum value of N is 10^3. But the constraints imply us to avoid repeated Calculations. So, we pre-Compute K\ \forall\ n \le N and strore them in array.
We also store the Cumulative sum (In other words, Prefix Sum) in another array.
That’s all.

3

Please ensure that whenever you post code on any forum you remove the template code as it makes it unnecessarily cumbersome and hard for the reader to understand.

4

Well, that’s completely my wish, whether to put with or without template. The template is not so difficult to read, though the considerable code is at the bottom. If it’s difficult to read, ask me, I may explain.

5

Yes definitely it’s your wish, I was just telling you the basic etiquette of forums which you seem to be unaware of that’s all.

1 Like
6

… but please ensure that the stripped-down code still compiles (and runs the same as the version with the template code) :slight_smile:

4 Likes
7

Thank you for enlightening me your highness. Here you go with template-free Code.

#include <stdio.h>
#include <math.h>

#define size 1003

int count[size] = {0};

int setBitCount(int n) {
    int c = 0;
    while(n>0) {
        c += n&1;
        n >>= 1;
    }
    return c;
}

int getCount(int n) {
    int c = setBitCount(n);
    int p = ((int)(log2(n))) + 1;
    return (1<<(p-c));
}

void preCompute() {
    for(int i=1;i<size;i++)
        count[i] = count[i-1] + getCount(i);
}

void solve() {
    int n, q;
    scanf("%d %d",&n, &q);
    for(;q>0;q--) {
        int l, r;
        scanf("%d %d",&l, &r);
        printf("%d\n", count[r] - count[l-1]);
    }
}

int main() {
    int t;
    scanf("%d",&t);
    preCompute();
    for(;t>0;t--) {
        solve();
    }
    return 0;
}