# 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.

Source: codewars | Difficulty: MEDIUM_HARD
Tags: Ad-hoc

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 < 2 and 'ODD') or (lambda b: s(n & ~b, k & ~b))(1 << n.bit_length() - 1)


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'


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'