Codeforces Round 647 Div 2 Problem C

15

one liner solution :slight_smile:

print (2*n - count_1_in_binary_of(2 * n ))

Here u go -

#include<bits/stdc++.h>
using namespace std;
#define lli long long int

lli cntones(lli n){
lli cnt=0;
while(n){
    if(n%2==0)cnt++;
    n/=2;
}
return cnt;
}

int main(){
lli t;
cin>>t;
while(t--){
     lli n;
     cin>>n;
     cout<<(2*n - cntones(2*n))<<endl;   // or cout<<(2*n - cntones(n))<<endl;
 }
 return 0;
}

If this type of questions occur in which there is a series like in this 1 3 4 7 8 10 11 then go to OEIS :—> A005187 - OEIS

1 Like
16

While accessing out of bounds (arr[61]), it also fills arr[0] with garbage value both on codeforces and my system (don’t know why??) but on codechef, arr[0]=1 and no garbage value is filled. I am not the right person to answer this as I have less knowledge of technicalities of c++ . You may ask any other experienced person. I’d also like to know.
maybe @galencolin

17

yep

1 Like
18

Bro I don’t need solution. I just want to know the reason of problem

19

This error due to internal precision and type casting .

20

or i think @ssjgz will help in this case :slight_smile:

1 Like
21

same pinch :slight_smile:

22

Ya…I forgot him…He must know.

23

I think he is not online now. I already tagged him at the start only.

24

I’d call it undefined behavior, but I don’t know what I’m talking about either… trust @ssjgz

3 Likes
25

wait for him…I am going to sleep. Good Night!!

1 Like
26

Let leave this to cc and cf and gud night

4 Likes
27

@galencolin a small question help me plzz …

Given two no. A and B check whether A! % B ==0 ? or not

0<= A , B <= 10^(18) ?

How can i do this

28

Was about to answer, but first, source please

29

I increase A and B to MAX ie., 10^ 18 then how can i solve

I use this : https://www.geeksforgeeks.org/largest-power-k-n-factorial-k-may-not-prime/

But it works only for N upto 10^12

30

I mean, you could just extend the given solution with fast factorization

31

and also above GFG approach not worked for this question…how can i do this and even for bigger constraints :thinking:

32

Ok the i use above link if i need for bigger constraints but for now how can i solve , the gfg approach gave TLE :frowning_face:

33

Replace their prime factorization with this, the one on that page is bad

34

Yeah it works …thanks @galencolin i will read fast prime facto … :slight_smile: