Find the K-th Character in String Game I

easy bit manipulation math recursion

Problem

Start with word = "a". One operation makes a copy of word with every letter shifted to the next letter of the alphabet, then appends that copy to the end. So "a" → "ab" → "abbc" → "abbcbccd", the length doubling each time. Given a positive integer k, return the k-th character (1-indexed) once word has at least k characters.

Inputk = 5

Output"b"

After three operations word = "abbcbccd"; the 5th character is "b". Equivalently, k−1 = 4 = binary 100, which has one set bit, so the answer is 'a' + 1 = 'b'.

k (1 to 500)

def kthCharacter(k):
    # The k-th char (1-indexed) is decided by position k-1.
    # Each "1" bit of k-1 means one alphabet shift was applied,
    # so the answer is 'a' shifted by popcount(k - 1).
    shifts = bin(k - 1).count("1")
    return chr(ord("a") + shifts)

function kthCharacter(k) {
  // Look at the 0-indexed position p = k - 1.
  // Count its set bits: each one is one alphabet shift.
  let p = k - 1, shifts = 0;
  while (p > 0) { shifts += p & 1; p >>= 1; }
  return String.fromCharCode(97 + shifts);
}

char kthCharacter(int k) {
    // Position p = k - 1; popcount(p) = number of shifts.
    int p = k - 1, shifts = 0;
    while (p > 0) { shifts += p & 1; p >>= 1; }
    return (char) ('a' + shifts);
}

char kthCharacter(int k) {
    // popcount of (k - 1) tells how many +1 shifts apply.
    int p = k - 1, shifts = 0;
    while (p > 0) { shifts += p & 1; p >>= 1; }
    return (char) ('a' + shifts);
}

Explanation

The naive route is pure simulation: keep doubling word until it reaches length k, then read word[k-1]. Because k ≤ 500 the string never grows past 512 characters, so this is perfectly fine and is exactly what the visualizer above acts out.

But there is a beautiful closed form. Look at how a position is built. The string of length 2^n is the string of length 2^(n-1) followed by a shifted copy of it. So a position in the second half is the same as the matching position in the first half, but with one extra shift.

Write the 0-indexed position p = k - 1 in binary. Each time we descend into a "second half" we strip the top set bit and add one shift. By the end, the total number of shifts applied to the original 'a' equals the number of 1 bits in p — its popcount.

So the answer is simply chr('a' + popcount(k - 1)). For k = 5: p = 4 = 100₂, popcount is 1, answer 'a' + 1 = 'b'. For k = 10: p = 9 = 1001₂, popcount is 2, answer 'a' + 2 = 'c'.

This turns an exponential-length construction into a couple of bit operations — constant time and constant space.

Time: O(log k) Space: O(1)