Help required for improving the program. | Sololearn: Learn to code for FREE!

+1

# Help required for improving the program.

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.

10/20/2021 11:24:27 AM

sanjit jha

+2

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

+2

Sorry, I just somehow missed it.

+1

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

+1

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!

+1

Thank you very much for your suggestion

+1

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));

0

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

0

*decimal value

0

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

0

Yess it always ends up close it. Nice observation🙂

0

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

0

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

0

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.

0

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