# Task
 Consider the following algorithm for constructing 26 strings S(1) .. S(26):
```
S(1) = "a";
For i in [2, 3, ..., 26]:
S(i) = S(i - 1) + character(i) + S(i - 1).```

 For example:
```
S(1) = "a"
S(2) = S(1) + "b" + S(1) = "a" + "b" + "a" = "aba"
S(3) = S(2) + "c" + S(2) = "aba" + "c" +"aba" = "abacaba"
...
S(26) = S(25) + "z" + S(25)```
Finally, we got a long string S(26). Your task is to find the `k`th symbol (indexing from 1) in the string S(26). All strings consist of lowercase letters only.

# Input / Output


 - `[input]` integer `k`

  1 ≤ k < 2^(26)


 - `[output]` a string(char in C#)

  the `k`th symbol of S(26)

Difficulty: introductory

Starter code:

def abacaba(k):
	

Solutions:
def abacaba(k):
    return next(chr(97+i) for i,d in enumerate(f'{k:b}'[::-1]) if d=='1')

def abacaba(k):
    return chr(96 + (k & -k).bit_length())

def abacaba(k):
    return chr((k & -k).bit_length() + 96)

def abacaba(k):
    n = 26
    if k % 2: return 'a'
    while k % pow(2, n) != 0: n -= 1
    return chr(97 + n)

def abacaba(k):
    alph = 'abcdefghijklmnopqrstuvwxyz'
    s = ''
    for i in range(26):
        s = s + alph[i] + s
    return s[k-1]
    
         


from string import ascii_lowercase

def abacaba(k):
    for i, c in enumerate(reversed(ascii_lowercase)):
        p = 2 ** (25 - i)
        if k == p:
            return c
        if k > p:
            k -= p


def abacaba(k):
    for i in range(26):
        if k%(2**(i+1)) == 2**i:
            return chr(i+97)


from functools import lru_cache

@lru_cache(maxsize=None)
def rec(i):
    if not i: return ""
    return rec(i-1) + chr(97+i-1) + rec(i-1)

def abacaba(k):
    return rec(26)[k-1]

def abacaba(k):
    k = k-1
    for i in range(1,27):
        if k%(2**i) == 2**(i-1)-1:
            return chr(96+i)