### mogermany's blog

By mogermany, history, 6 weeks ago,

Hi everbody I have a problem with a codefoeces task called "Even Odds" 318A - Even Odds with python My code do not work with the test number 8

that is my code

####

#### print(create(n, k-1))

Can u help me please ?

• -1

 » 6 weeks ago, # |   0 Your method of listing it out is inefficient. n can go up to 10^12 which will cause your method to exceed time and memory limits. You should instead calculate (if k is less than ceil half of n, which odd number? Else which even number?)
 » 6 weeks ago, # |   0 Hi, your solution takes more time and space. Because the function $create(n, k)$ is $O(n)$ time and space complexity. it's fine when $n$ is too small. But here $n \le 10^{12}$Instead of actually creating those odd and even arrays seperately we can make some observations.Let's consider the case when $n$ is even. we write numbers in form : $1, 3, 5, \dots, n-1, 2, 4, 6, \dots, n$. Here $n$ is even so $n-1$ will be the last odd numberSince $n$ is even there are exactly ${n / 2}$ Odd numbers and ${n / 2}$ even numbers. so the odd numbers are in range $[1, n / 2]$ and even numbers are in range $[n / 2 + 1, n]$. So if $k$ is in the range $[1, n/2]$ ($k$ $\epsilon$ $[1, n/2]$)then the $k-th$ element is odd otherwise it's an even number. $i-th$ odd number is $2 \cdot i - 1$, here $i = k$. So answer is $2 \cdot k - 1$.now if $k \gt n/2$, then answer is even number. even numbers start after first $n/2$ elements so to get positioning of even numbers from $1$ we must subtract the count of odd numbers. $i-th$ even number is $2 \cdot i$, here $i = k - (n / 2)$. So answer is $2 \cdot (k - (n / 2))$.This way you can do for the case when $n$ is an odd number. You will see that you need some ceiling of $n/2$ in solution.If my solution or idea is wrong feel free to point out. Thanks:)