Fact that vertices in a group are odd multiples of first term can be easily understood by the fact that all other set bits other than bit at position i are even multiple of 2^i i.e. first term(think in terms of left shift).
1 Like
For all who want to understand in more shorter manner Commented code with understable variables 
See : CodeChef: Practical coding for everyone
Any doubt Plz ask
2 Likes
I had a similar approach. It’s probably an extension of the solution mentioned here.
First of all, check if N is a power of 2. If no, we can proceed further.
Connect all the odd numbers (> 1) to 1. This will add N-N/2-1 to the answer.
Now there’s an observation: For an integer X which is not a power a 2, if it is divisible by 2^y (y\geq 1), then the y^{th} bit of X will be the lowest set bit in X. So for such an integer X, we add 2^y to the answer.
If an integer X is a power of 2, we can simply connect it with X+1 (which is odd). And for such an integer X, we add X to the answer.
Now, if you observe carefully, all odd numbers are connected to each other, and all powers of 2 are connected to some odd number, and finally, all the remaining numbers are connected to some power of 2. Thus, we have managed to connect all the integers from 1 to N.
Refer this for better understanding.
5 Likes
“The minimum positive cost with which a vertex numbered x can be connected to some vertex in the graph is equal to the value of the lowest set bit in x”
can you please explain why ?
like if I take 14 and 6 as example, the LSB is 2 for both, How could we have a road in bw those so the cost is 2 ?
You got it wrong. For some vertex numbered x, it is possible to choose to another vertex y which will give minimum cost equal to value of lowest set bit in x.
And if we follow this property for every vertex, then, out total cost will be minimum.
That’s why for x = 14, you cannot take y = 6 because cost here will be 6 instead of 2.
Check out my video editorial for better understanding.
Nice Editorial.
1 Like
My approach was entirely different. You can notice a pattern repeats at every 2^i. I pre-calculated answer for all 2^i in a vector ans . And simplified result\; += ans[ \text{power of 2 just below N}] and now N = N\; \% \; \text{power of 2 just below N} . Keep on calculating till N reaches 1 or 0.
Submission : CodeChef: Practical coding for everyone
We are not connecting 14 to 6 by a direct edge. The lowest set bit in x is like a limit for it, as in, it is not possible to make a vertex connected to the graph with a cost of less than the value of its lowest set bit.
14 and 6 have bits of value 2 and value 4 common. It doesn’t mean that we are connecting them. Since their lowest set bit is common, we are simply placing them inside the same connected component, i.e., the component of vertex 2. They will be connected to 2 by a direct edge, and this will cost 2.
Did exactly the same … 
How did you come up with the formula of V ?
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