Thanks for this, I was so confused!
1 Like
I just used log for the powers of two… it won’t affect the answer though bcoz eventually in the while loop it will get 1and at the end 0… still it did sped up my code (not overall but still) by reducing few test cases to O(1) from O(logn)
solution link:
https://www.codechef.com/viewsolution/53887828
my IDE is giving me correct answers on the test cases but on codechef …it is showing as the wrong answer…can you point out the mistake…
#include<stdio.h>
int divide(long long int a,long long int b);
int main()
{
long long int t;
long long int temp =0,ts;
scanf("%d",&t);
int arr[t];
for(long long int i=0;i<t;i++)
{
scanf("%lu",&ts);
for (long long int j=1;j<=ts;j++)
{
int c = divide(j,ts);
if(c==0)
{
temp++;
}
}
arr[i]=temp;
}
for(int i=0;i<t;i++)
{
printf("%d\n",arr[i]);
}
}
int divide(long long int a,long long int b)
{
if((a%2)==0 &&(b%2)==0)
{
divide(a/2,b/2);
}
if(a==1||b==1)
{
return 1;
}
else if ((a%2)==0&&(b%2)!=0)
{
return 0;
}
else if((b%2)==0&&(a%2)!=0)
{
return 1;
}
else
{
return 1;
}
}