It gives number of set bits. All powers of 2 have only 1 bit set.
1 Like
Look at my solution in Python. I believe it’s extremely efficient and intuitive.
Why it’s showing WRONG ANSWER?
#include
using namespace std;
int find(long int n)
{
if(n==10 || n==20)
return 1;
else if(n%10!=0)
return 0;
find(n/20);
find(n/10);
}
int main()
{
int t;
cin>>t;
while(t–)
{
long int n;
cin>>n;
int a=find(n);
if(a==1)
cout<<“YES”<<endl;
else
cout<<“NO”<<endl;
}
}
your find(n/20);
and find(n/10);
will never be called.
Your code will only show YES for n=10 or n=20.
Suppose there is n=30,40,50,60…
Then find(n/20) and find(n/10) is being called.
And in my editor also it’s showing correct output for almost all test cases.But codechef submission gives WA.
Change your base case to this-
if(n==original||original==1)
it will work
very nice setter solution
Hey I have a similar solution. We multiply the number with either 10 or 20 . If we keep multiplying with 10 then we can easily check by dividing the number with 10 until we get 1.
If we multiplied the no with 20 then then after removing all the zeroes from the right of the number must be a power of two. So keep dividing the number by 2 until we get 1. If we dont get one the answer is NO.
Here’s my solution
#include<bits/stdc++.h>
#define vll vector
#define ll long long
#define mp make_pair
#define pb push_back
#define mod 1000000007
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); //fast I/O
ll t;cin>>t;
while(t–)
{
ll n;cin>>n;
ll flag=1;
if(n==1)
{
cout<<“Yes\n”;
flag=0;
continue;
}
else if(n%10!=0)
{
cout<<“No\n”;
continue;
}
else
{
ll zero_cnt=0,power_cnt=0;
while(n%10==0)
{
n/=10;
zero_cnt++;
}
if(n==1)
{
cout<<“Yes\n”;
flag=0;
continue;
}
else
{
while(n%2==0)
{
n/=2;
power_cnt++;
}
if(n==1 && zero_cnt>=power_cnt)
{
cout<<“Yes\n”;
flag=0;
continue;
}
else
{
cout<<“No\n”;
continue;
}
}
}
}
return 0;
}
@taran_1407 For bonus problem, I feel 1st condition is N%X==0 and then prime factorisation of N/X should only contain primes in range [1,K].
If N/X ~ 10^12, we can prime factorise it in sqrt(N) and give answer in O((N/X)0.5) irrespective of K.
If N/X ~ 10^18, we can check all values in range [1,K], and keep on dividing it. It we have number 1, answer is yes, No other wise. complexity is O( K *or+ log(N) ) this time.
Is there any other solution i am missing?
hey ! please help me in identifying the problem with this code. it works fine for all the test cases i tried but the verdict is still wrong ans.
(1zRMha - Online C++0x Compiler & Debugging Tool - Ideone.com)
Hey @lil_ninja !
You should print Yes and No
instead of YES and NO
Be careful from next time
Sudheera Y S
1 Like
yes, sure
thanks a lot, thought about it a lot and now this being the error made me facepalm
why tagging me in this code. also never send codes, share link. It makes it harder to scroll 100s of lines!
what is wrong in this code?
t= int(input())
def fun(n):
ans=0
if (n==10):
return 10
if(n==20):
return 20
if(n<10):
return 0
if (n>10 and n<20):
return 0
if(n%10==0 or n%20==0):
ans=ans+fun(n//20)+fun(n//10)
return ans
for i in range(t):
n= int(input())
ans=fun(n)
if(ans==10 or ans==20 or ans==30):
print("Yes")
else:
print("No")I have also done this question by this method and it is accepted but not previous one
import math
t= int(input())
def Log2(x):
if x == 0:
return false;
return (math.log10(x) /
math.log10(2));
def isPowerOfTwo(n):
return (math.ceil(Log2(n)) ==
math.floor(Log2(n)));
for i in range(t):
n= input()
count=len(n)-len(n.rstrip(“0”))
a=n.rstrip(“0”)
if isPowerOfTwo(int(a)) and (count>=math.ceil(Log2(int(a)))):
print("Yes")
else:
print("No")Editorialist’s solution was clearer though…
Check for n = 1
the answer is Yes but I think your code will give output No
So change this and it will work hopefully
Sudheera Y S
