# Task
 You are given integer `n` determining set S = {1, 2, ..., n}. Determine if the number of k-element subsets of S is `ODD` or `EVEN` for given integer k.

# Example

 For `n = 3, k = 2`, the result should be `"ODD"`
 
 In this case, we have 3 2-element subsets of {1, 2, 3}:
 
 `{1, 2}, {1, 3}, {2, 3}`

 For `n = 2, k = 1`, the result should be `"EVEN"`.
 
 In this case, we have 2 1-element subsets of {1, 2}:
 
 `{1}, {2}`

 `Don't bother with naive solution - numbers here are really big.`

# Input/Output


 - `[input]` integer `n`

    `1 <= n <= 10^9`


 - `[input]` integer `k`

    `1 <= k <= n`


 - `[output]` a string

    `"EVEN"` or `"ODD"` depending if the number of k-element subsets of S = {1, 2, ..., n} is ODD or EVEN.

Difficulty: interview

Starter code:

def subsets_parity(n,k):
	

Solutions:
def subsets_parity(n, k):
    return 'EVEN' if ~n & k else 'ODD'

subsets_parity=lambda n,k:~n&k and"EVEN"or"ODD"

subsets_parity=s=lambda n,k:n<k and"EVEN"or n<2and"ODD"or(lambda b:s(n&~b,k&~b))(1<<n.bit_length()-1)

#Courtesy of giants :D
def subsets_parity(n,k):
    N,K = bin(n)[2:][::-1], bin(k)[2:][::-1]
    for i in range(len(K)):
        if K[i] > N[i]:
            return 'EVEN'
    return 'ODD'

#using lucas's theorem https://en.wikipedia.org/wiki/Lucas%27s_theorem

def to_bin(n):
    k = 0
    while n >= 2**k: k += 1
    s = ""
    for i in range(k - 1, -1, -1):
        if n - 2**i >= 0: 
            s += "1"
            n -= 2**i
        else: s += "0"
    return s

def subsets_parity(n, k):
    s1 = to_bin(n)
    s2 = to_bin(k)
    for i in range(-1, -len(s2) - 1, -1):
        if s1[i] == "0" and s2[i] == "1": return "EVEN"
    return "ODD"

def subsets_parity(n,k):
    string_set = "{:02b}".format(n)
    length = len(string_set)
    string_subset = "{:02b}".format(k).zfill(length)
    for i in range(0, length):
        if not int(string_set[i]) and int(string_subset[i]):
            return "EVEN"
            break
    else:
        return "ODD"

import math

def f1(n):
    x,s=1,0
    while 2**x<=n:
        s=s+ math.floor(n/2**x)
        x=x+1
    return (s)

def subsets_parity(n,k):
    if n==k:
        return "ODD"
    if n>0 and k>0 and n-k>0:
        if f1(n) == f1(k) + f1(n-k):
            return "ODD"
        else:
            return "EVEN"
        
    


def subsets_parity(n,k):
  while k:
    if not n & 1 and k & 1: return 'EVEN'
    n, k = n // 2, k // 2
  return 'ODD'

def c(n):
    m = 0
    while n > 0:
        n = n // 2
        m += n
    return m

def subsets_parity(n,k):
    return "EVEN" if (c(n)-c(k)-c(n-k))>0 else "ODD"

def subsets_parity(n,k):
    return 'ODD' if n==k|(n-k) else 'EVEN'