mogermany's blog

By mogermany, history, 7 weeks ago, In English

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

def create(n,k):

numbers=[]

i = 1

o = 1

while i <= n:

if i%2 != 0:

numbers.append(i)

i+=1

while o <= n:

if o%2 == 0:

numbers.append(o)

o+=1

return numbers[k]

####

n, k = map(int, input().split())

print(create(n, k-1))

Can u help me please ?

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 number

Since $$$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:)