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: CodeChef: Practical coding for everyone
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.
So, you want him to help you during the exam.
If possible anyone at that time
This is ridiculous. How can you ask someone to help you with an assessment?
HackwithInfy is an assessment, right?