Skip to content

3307. Find the K-th Character in String Game II 👍

  • Time: $O(\log k)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  char kthCharacter(long long k, vector<int>& operations) {
    const int operationsCount = ceil(log2(k));
    int increases = 0;

    for (int i = operationsCount - 1; i >= 0; --i) {
      const long halfSize = 1L << i;
      if (k > halfSize) {
        k -= halfSize;  // Move k from the right half to the left half.
        increases += operations[i];
      }
    }

    return 'a' + increases % 26;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public char kthCharacter(long k, int[] operations) {
    final int operationsCount = (int) Math.ceil(Math.log(k) / Math.log(2));
    int increases = 0;

    for (int i = operationsCount - 1; i >= 0; --i) {
      final 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);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def kthCharacter(self, k: int, operations: list[int]) -> str:
    operationsCount = math.ceil(math.log2(k))
    increases = 0

    for i in range(operationsCount - 1, -1, -1):
      halfSize = 2**i
      if k > halfSize:
        k -= halfSize  # Move k from the right half to the left half.
        increases += operations[i]

    return string.ascii_lowercase[increases % 26]