yeah the logic is sound…
what was the result?
i tried running your code on online IDE but its giving EOF error dunno why
my approach:
t = int(input())
for i in range(t):
…ts = int(input())
…if ts % 2 == 0:
…while(ts % 2 == 0):
… ts = ts // 2
…j = (ts - 1) // 2
…else:
…j = (ts - 1) // 2
print(j)
upd : for PYTH 3.6, use N//2 instead of int(N/2) or (N-1)/2
What a bad explanation
1 Like
video Explanation>>>
AC, both subtasks.
I did it using a different approach i solved the subtasks having considering three cases : first if the number (ts) is odd then answer will be floor(ts/2) and if the number (ts) is even then the number will either be a power of two or not a power of two . If the number is a power of two then the answer is 0 otherwise if the number is not a power of two then we simply divide the number until the number becomes odd and when the number becomes odd the answer will (ts)/2 as it was done in case 1.
Solution Link: CodeChef: Practical coding for everyone
Python 3.6
TS = TS/2 (i)
using above statement gives zero in subtask2 that is original constraints (1≤T≤10^5* 1≤TS≤10^18)
but if you use
TS = TS//2 (ii)
it passes with 100% score.
Because in (ii) you are storing TS as integer while in (i) its float which requires more memory in storage.
Hi ,
Can anyone help me with this .
what am I doing wrong , it is giving TLE for 2nd test case when I am using floor Function and same logic without floor is getting accepted.
https://www.codechef.com/viewsolution/34468313
for _ in range(int(input())):
ts=int(input())
if ts%2==0:
while(ts%2!=1):
ts=ts/2
if ts%2!=0:
print(int(ts//2))
Can anyone suggest what is wrong in this implementation ?? Logic is exactly same but 2nd test case is not passing while submitting. Any help is appreciated. Thank you.
To find 2^i we can also do (TS & -TS) right? So it’s O(1) per test case?
Same issue bro i have also used this same approach
We can do it in one line : O(1)
Answer: TS / ((TS & ( (~TS) + 1)) << 1);
where TS is input, Tom Strength
any corner cases in the question
No
I am getting TLE , can anyone help me to optimize my code.
import java.util.ArrayList;
import java.util.Scanner;
public class ChefAndStrings {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int t = s.nextInt();
for (int i = 0; i < t; i++) {
int c = 0, evan_c = 0;
ArrayList<Integer> arr = new ArrayList<>();
int ts = s.nextInt();
for (int j = 2; j < ts; j++) {
if (j % 2 == 0) {
arr.add(j);
c++;
}
}
if (ts % 2 != 0) {
System.out.println(c);
} else {
while (ts % 2 == 0 || ts > 0) {
ts /= 2;
}
if (ts == 0) {
System.out.println(0);
} else {
for (int k = 0; k < arr.size(); k++) {
if (arr.get(k) / 2 < ts && arr.get(k) % 2 == 0)
evan_c++;
}
System.out.println(evan_c);
}
}
}
}
}
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;
}
}