Help required for improving the program.

Question

Given an integer input of Length N A set is formed of numbers 1 to N like {1,2,3,4,...,N} Find the length of longest subset S1 that can be formed such that if S1 contains x then it should not contain 2x.

I made an attempt at solving it and was able to complete 7/9 test cases but the last 2 test cases ended as time limit error and segmentation fault. How can I improve the code to complete the remaining test cases.

Answer 1

https://code.sololearn.com/cpI05Vxwt21a/?ref=app

Answer 2

Sorry, I just somehow missed it.

Answer 3

And how exactly are people supposed to help improve a program without seeing it?

Answer 4

I found optimizations to your implementation, though I did not verify whether the algorithm correctly meets the challenge.

Line 14 can skip even numbers and double the speed. Change from
for(int i=0;i<a;i++){
to
for(int i=1;i<a;i+=2){

Maybe better yet, empirically I observed the resulting answer seems to be always round(2N/3). If that is a general rule, then you could shorten your main code to 3 lines!

Answer 5

Thank you very much for your suggestion

Answer 6

What happens if you try the rounded calculation approach? And just to be safe, try using long instead of int in the declarations.

For example,
printf("%ld", (long)(2.0*a/3.0 + 0.5));

Answer 7

The problem in deriving a general rule is if 2N/3 is a float value it sometimes takes ceil value while other times it takes floor values

Answer 8

*decimal value

Answer 9

My observation was that the answer was neither ceil nor floor, but consistently the rounded decimal value.

Answer 10

Yess it always ends up close it. Nice observation🙂

Answer 11

Also I made the necessary modifications but it still gives time limit error

Answer 12

In case of rounded calculation for half of the test case the formula mentioned by you works and for others 2*a/3-0.5 works

Answer 13

sanjit jha you mentioned getting a segmentation fault. That happens when accessing memory out of bounds. I suspect that they are giving very large numbers for N, which might cause overflow when storing N into int a and it becomes negative. Try using unsigned int, or long, or unsigned long.

Answer 14

I had tried it but it only results in time limit error.