3307. Find the K-th Character in String Game II
Approach
Find highest set bit of k; trace back through operations to determine character.
Key Techniques
Math problems test number theory, combinatorics, and modular arithmetic. Common tools: GCD/LCM (Euclidean algorithm), prime sieve, modular inverse (Fermat's little theorem), digit manipulation, and bit tricks. Overflow is a key concern in C# — use long when products may exceed 2³¹.
Bit manipulation uses bitwise operators (&, |, ^, ~, <<, >>) for compact and fast solutions. Key tricks: x & (x-1) clears lowest set bit, x ^ x = 0 (XOR cancellation), and bitmask DP represents subsets as integers. In C#, use int (32-bit) or long (64-bit) for bitmasking.
Recursion solves a problem by calling itself with a smaller sub-problem. Every recursive solution needs: a base case (to stop) and a recursive case (to reduce). Stack space is O(depth). Convert deep recursion to iteration with an explicit stack when stack overflow is a concern.
// Approach: Find highest set bit of k; trace back through operations to determine character.
// Time: O(log k) Space: O(log k)
public class Solution
{
public char KthCharacter(long k, int[] operations)
{
int operationsCount = (int)Math.Ceiling(Math.Log(k) / Math.Log(2));
int increases = 0;
for (int i = operationsCount - 1; i >= 0; --i)
{
long halfSize = 1L << i;
if (k > halfSize)
{
k -= halfSize; // Move k from the right half to the left half.
increases += operations[i];
}
}
return (char)('a' + increases % 26);
}
}