i am unable to understand the logic for
lli total_element_whose_i_th_bit_set = (n+1)/2;
and n = n/2;
Can you please tell me how you got these ?
Read comments bro 
I think i mentioned all the things clearly
Just sharing my commented code .
Code
#include <bits/stdc++.h>
using namespace std;
//the following array contains powers of 2. Index 1 will contain 2^1 = 2, and so on
long long two[35] = {0};
bool Compare(long long n) { //a function to check whether the given number is a power of 2 or not
for(long long i = 0; i < 35; i++) {
if(two[i] == n)
return true;
}
return false;
}
void Solve() {
long long n; //inputting n
cin >> n;
if(Compare(n)) { //if n is a power of 2, answer is -1
cout << "-1" << endl;
return;
}
long long ans = 0;
for(long long i = 0; i < 34; i++) {
if(two[i] > n) //don't require further iterations
break;
long long start = two[i] + two[i + 1]; //first number which will be connected to 2^i(there is a pattern if you observe)
if(start > n) { //if the number is greater than n
ans += two[i]; //to connect the graph
continue;
}
long long lol = (n - start) / two[i + 1] + 1; //this integer basically stores the count of numbers which the current element has to be connected with
ans += (two[i] * lol); //for all the numbers, two[i] must be added each
if(i != 0) //if i == 0, we don't have to connect the number to anything else
ans += two[i]; //else we need to connect the graph
}
cout << ans << endl;
}
void power() {
two[0] = 1;
two[1] = 2;
for(long long i = 2; i <= 35; i++) {
two[i] = two[i - 1] * 2;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
power();
int t;
cin >> t;
while(t--) {
Solve();
}
return 0;
}
why are u adding 2^y to the solution ā¦ this part is unclear ā¦ can u please help?
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define MAX 100050
bool ispower2(lli n){
return(n and (n&(n-1))==0 );
}
int main(){
fastio
lli t=1;
cin>>t;
while(t--) {
lli n;
cin>>n;
if(ispower2(n))
cout<<-1<<endl;
else{
// first count odd element means those elements whose 0'th bit is set (from right)
// like 1,3,5,7,9,11, but we have to connect all odd to 1 so
// contribution is (count of odd-1)
lli ans = (n+1)/2;
ans-=1; // odd element who contributed;
// remaining no. are half of initial
n=n/2;
//Now we have to calculate contribution of 2^i (i>=1) means i'th bit from right
// those values whose 1st bit is set (except already taken in odd element) is 2 6 10 14 ...
// contribution of this again as same as above we have to connect all element(whose 1st bit is set) to 2
// 2<-6 , 2<-10 ...
// so contribution is (no of element whose 1st bit is set)-1 * 2^1
// but now one thing 6,10,14 are connected to 2 but how can i reach node 3 from node 2
// so we have to connect only one node from 2 to 3 so connect 2<-3 that means add (2&3) in above to
// that means
//(no of element whose 1st bit is set)-1 * 2^1 + (2&3) = (no of element whose 1st bit is set)-1 * 2^1 +2 = (no of element whose 1st bit is set)*2^1
// now again half and calculate similarly for contribution of 2^2 means 2nd bit set from right
// those values whose 2nd bit is set (except already taken in odd element and except already taken element whose 1st bit is set
// is 4 12 20 28 .....
// contribution of this again as same as above we have to connect all element(whose 2nd bit is set) to 4
// 4<-12 , 4<-20 , 4<-28
// so contribution is (no of element whose 2nd bit is set)-1 * 2^2
// but now one thing 12,20,28 are connected to 4 but how can i reach node 4 from node 5
// so we have to connect only one node from 4 to 5 so connect 4<-5 that means add (4&5) in above to
// that means
//(no of element whose 2nd bit is set)-1 * 2^2 + (4&5) = (no of element whose 2nd bit is set)-1 * 2^2 +4 = (no of element whose 2nd bit is set)*2^2
// and this process is going on
lli i=1;
while(n){
lli total_element_whose_i_th_bit_set = (n+1)/2;
lli contribution = total_element_whose_i_th_bit_set * (1<<i);
ans = ans + contribution;
n/=2;
i++;
}
cout<<ans<<endl;
}
}
return 0;
}
1 Like
I dont know what is wrong in my approach ; My approach is that if we have given a number then first check if itās a power of two if it is then print -1 if itās not then what i did is i connect all the odd numbers to 1 so ans till this point will be number of odd numbers uptill that point not including 1.
Then for the even number simply add thier lowest set bit which i found using (x&-x) and add it in my final answer ? I donāt see anything wrong in logic but still itās giving me WA can someone help.
Link to my code ā CodeChef: Practical coding for everyone
Let X=12. The highest power of 2 that divides X is 4 (=2^2). Now, observe the binary representation of 12, which is 1100. The lowest set bit is the 2^{nd} bit from the right (consider 0-based indexing). Now, if you take the AND of 12 & 4, you get 4. So basically, you need to add the lowest set bit, which is nothing but 2^y. I hope this clears things. Try some more examples to convince yourself.
while(pw)
{
ll tmp=pow(2,pw);
ll x=n/tmp;
x-=cur;
ans+=x*tmp;
cur+=x;
pwā;
}
I cannot understand this part of codeā¦ can u please show the dry run ā¦ the rest is clear
mean how u r calculating the amount to be added in the ans.
ans+=x*tempā¦whats the logic behind this? i found that all odd numbers contributed 1 to the sum, so thats n/2 . then also if n is power of 2, graph cant be connected. how did you
connect the even numbers.
We canāt find the highest power of 2 that divides X for every X from 1 to N. So weāll try to do something different. Find the count of all numbers that are divisible by a power of 2.
Let N=10. The highest power of 2 present in the range [1,N] is 8. How many numbers are there which are divisible by 8? The answer is N/8=10/8=1. That one number contributes 1*8=8 to the answer. The second highest power of 2 present is 4. How many numbers are there which are divisible by 4? The answer is N/4=10/4=2. But we are also counting the numbers divisible by 8 again. We need to subtract those. In the code, cur does this work. Therefore the count now becomes 2-1=1. We update answer as ans=ans+(1*4). And so on. Notice that in this process we calculated the contribution for all even numbers. Hope it is clear now.
1 Like
All odd numbers (>1) are connected to 1. All powers of 2 are connected to some odd number. More specifically, if X is a power of 2, then it can be connected to X+1 (which is odd). Finally, all the remaining even numbers are connected to some power of 2. More formally, if X is an even number which is not a power of 2, connect it to the highest power of 2 that divides it.
Crystal clear ā¦ Thank youā¦ 
Crystal Clearā¦ Thank youā¦
bro the solution was nice but at last in code when you are
lli contribution = total_element_whose_i_th_bit_set * (1<<i); doing this you are not actually chamging the value so when i=1 by shifting it becomes 2 but the actual value still remains to 1
then later you are increasing the value of i by 1 so it becomes 2 but when it is shifted it becomes 3 not 4 .
plz comment if i am right or wrong and also how should train myself to get the solution by seeing the question like this
bro 1<<i simply means 2^i (^ denotes power) so in each step I have to multiply 2^1 then 2^2 and so on .
(no of element whose 1st bit is set)-1 * 2^1 +2 = (no of element whose 1st bit is set)*2^1
Can you explain how that -1 is eliminated ?
(x-1)*y + y = ?
1 Like
I used a little different approach.
In the range 1 - N,
For numbers with LSB set at 0th position (ā¦1), we can connect them to 1 -> as these numbers & 1 = 1 which is lowest positive possible. Clearly there will be (N + 1) / 2 such numbers (half even and half odd) and their & with 1 = 1. And now removing such numbers, left out numbers = N / 2
For numbers with LSB set at 1st position (ā¦10), we can connect them to 2 -> as with 1 they will give & = 0, so their & with 2 will give 2. Also we can see N / 2 as shifting the bits to right by 1. So basically (ā¦10) is now (ā¦1) i.e. last bit as 1. Clearly their count is again half of left numbers (half even and half odd).
Finally by adding all the product of &s with eligible numbers count to the answer until left numbers is 0, we get the answer.
Here is my Approach
There exists an AP for every cost = 2^k (minimum in an AND operation)
COST | NODES
|
1 | 1, {3,5,7,9,.........}
| root connected with 1
|
2 | 2, {6,10,14,18,......}
| connected with 3 connected with 2
|
4 | 4 {12,20,28,36......}
| connected with 5 connected with 4
...............................................
...............................................
...............................................
c | c {3c,5c,7c,9c......}
connected with c+1 connected with node c
Now we can sum all the costs in range
1 Like
thnks a lotā¦