# Crack the Code by CognoAI

I gave this coding competition by CognoAI. Here is the link Programming Problems and Competitions :: HackerRank . It got over yesterday. Since the editorials are not out , will u guys tell me how to go about solving Programming Problems and Competitions :: HackerRank and Programming Problems and Competitions :: HackerRank . Thanks!

Approach for Bit Count 2

Before we get into the solution, let’s understand few things:

• Let X = A \oplus B, where \oplus represents Exclusive OR operator. Then

• X will have an even number of set bits if any one of the following conditions holds true

• Both A and B have an even number of set bits
• Both A and B have an odd number of set bits
• Similarly, X will have an odd number of set bits if any one of the following conditions holds true

• A has an even number of set bits while B has an odd number of set bits
• B has an odd number of set bits while A has an even number of set bits

Think why?

We will keep track of number of Integers with an even number of set bits (say even_count) and also number of integers with an odd number of set bits (say odd_count). For every query, we will update these variables accordingly and compute the answer. The number of pairs we can get is given by:

pairs = (even_count * (even_count - 1)) / 2 + (odd_count * (odd_count - 1)) / 2;
// Simple Combinatorics formula.


Now, it’s just implementation of the above logic

C Code
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {

int n;
scanf("%d", &n);
int a[n];
for(int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
int even_count = 0;
int odd_count = 0;
for(int i = 0; i < n; i++) {
int temp = a[i];
int c = 0;
while(temp > 0) {
c += temp % 2;
temp /= 2;
}
if(c % 2) {
odd_count ++;
}
else {
even_count ++;
}
}
int q;
scanf("%d", &q);
for(int i = 0; i < q; i++) {
int ind, val;
scanf("%d %d", &ind, &val);
int prev = a[ind];
int c = 0;
while(prev > 0) {
c += prev % 2;
prev /= 2;
}
if(c % 2) {
odd_count --;
}
else {
even_count --;
}
a[ind] = val;
c = 0;
while(val > 0) {
c += val % 2;
val /= 2;
}
if(c % 2) {
odd_count ++;
}
else {
even_count ++;
}
long long int ans = 0;
ans = ans + (((long long int) (odd_count)) * (odd_count - 1)) / 2;
ans = ans + (((long long int)(even_count)) * (even_count - 1)) / 2;
printf("%lld\n", ans);
}
return 0;
}


Similar Problem: Contest Page | CodeChef

4 Likes

Nice Observation ! wow.

I don’t have a clever solution for matrix problem but you can always binary search the answer though.

#include "bits/stdc++.h"
using namespace std ;
#define int long long
signed main(){
int n,k ;
cin >> n >> k ;--k;
auto ok = [&](int x)->int{
int c=0 ;
for(int i=1;i<=n;i++)
c+=min(x/i,n) ;
return c<=k  ;
} ;
int lb = 1,rb=n*n ;
while(lb<rb){
int mb=(lb+rb)/2 ;
if(ok(mb))
lb =mb+1 ;
else
rb=mb  ;
}
cout << lb  ;
}


1 Like

It would be great if you could tell me the logic. I dont get it from the code. Thanks

See you if I give you a number x then you can check whether it’s the kth number or not by counting the total number of elements which are less than x but are present in the matrix. You can do so by going to each ith row and adding \displaystyle\frac{x}{i} as it’s contribution. And rest is trivial binary search.

1 Like

Going through each row and adding x/i ? I still dont get it

Alright if you observe the matrix for any N it’d look like.
1 \ 2 \ 3 \ 4 \ \ 5 \dots\
2 \ 4 \ 6 \ 8 \ 10 \dots
3 \ 6 \ 9 \ 12 \ 15 \dots
\vdots
It is clearly evident that the ith row contains multiples of i.
Second thing to note is the following question.
How many multiples of i do we have which are less than a given number x.
If you scribble it on paper you can observe that it is exactly \displaystyle\frac{x}{i}. And we can also see it intuitively that why is this the case.
But again we cannot include more than N multiples for any row. Why ? as the number of columns in the matrix is exactly N and the highest multiple that we’ll have in a row will be i \times N so we take we consider min(\displaystyle \frac{x}{i},N) as the contribution from every row. Feel free to ask if you have any doubts.

1 Like

Thanks for taking the trouble of explaining it to me

1 Like

How to solve Raj and Vikash Problem. Im getting TLE.

Thank You @cubefreak777. Cubefreak777 do you help me as I have Hackwithinfy exam on may5?