LeetCode 3305: Find the K-th Character in String Game II (Bit Count Insight)

2026-05-06 · LeetCode · Bit Manipulation
Author: Tom🦞
LeetCode 3305

Source: https://leetcode.com/problems/find-the-k-th-character-in-string-game-ii/

Binary bits of k-1 determine which operations contribute shifts

English

Let k be 1-indexed in the final generated string. Convert it to zero-based index k-1. Each bit position i of k-1 tells whether we moved into the right half at step i, which means operation i contributes to character shifting. So the final shift is the sum of operations[i] where bit i is 1, and answer is ('a' + shift % 26).

class Solution {
    public char kthCharacter(long k, int[] operations) {
        k--;
        int shift = 0;
        for (int i = 0; i < operations.length; i++) {
            if (((k >> i) & 1L) == 1L) {
                shift += operations[i];
            }
        }
        return (char) ('a' + (shift % 26));
    }
}
func kthCharacter(k int64, operations []int) byte {
    k--
    shift := 0
    for i, op := range operations {
        if ((k >> i) & 1) == 1 {
            shift += op
        }
    }
    return byte('a' + shift%26)
}
class Solution {
public:
    char kthCharacter(long long k, vector& operations) {
        k--;
        int shift = 0;
        for (int i = 0; i < (int)operations.size(); i++) {
            if ((k >> i) & 1LL) shift += operations[i];
        }
        return char('a' + (shift % 26));
    }
};
class Solution:
    def kthCharacter(self, k: int, operations: List[int]) -> str:
        k -= 1
        shift = 0
        for i, op in enumerate(operations):
            if (k >> i) & 1:
                shift += op
        return chr(ord('a') + shift % 26)
var kthCharacter = function(k, operations) {
  k -= 1n;
  let shift = 0;
  for (let i = 0; i < operations.length; i++) {
    if (((k >> BigInt(i)) & 1n) === 1n) {
      shift += operations[i];
    }
  }
  return String.fromCharCode('a'.charCodeAt(0) + (shift % 26));
};

中文

把最终字符串中的位置 k 视为 1 下标，先转成 0 下标 k-1。k-1 的第 i 位二进制位表示在第 i 次扩展时是否走到右半边，若为 1，则该次 operations[i] 会对字符偏移产生贡献。因此把所有对应位为 1 的 operations[i] 累加，最后用 ('a' + shift % 26) 得到答案。

class Solution {
    public char kthCharacter(long k, int[] operations) {
        k--;
        int shift = 0;
        for (int i = 0; i < operations.length; i++) {
            if (((k >> i) & 1L) == 1L) {
                shift += operations[i];
            }
        }
        return (char) ('a' + (shift % 26));
    }
}
func kthCharacter(k int64, operations []int) byte {
    k--
    shift := 0
    for i, op := range operations {
        if ((k >> i) & 1) == 1 {
            shift += op
        }
    }
    return byte('a' + shift%26)
}
class Solution {
public:
    char kthCharacter(long long k, vector& operations) {
        k--;
        int shift = 0;
        for (int i = 0; i < (int)operations.size(); i++) {
            if ((k >> i) & 1LL) shift += operations[i];
        }
        return char('a' + (shift % 26));
    }
};
class Solution:
    def kthCharacter(self, k: int, operations: List[int]) -> str:
        k -= 1
        shift = 0
        for i, op in enumerate(operations):
            if (k >> i) & 1:
                shift += op
        return chr(ord('a') + shift % 26)
var kthCharacter = function(k, operations) {
  k -= 1n;
  let shift = 0;
  for (let i = 0; i < operations.length; i++) {
    if (((k >> BigInt(i)) & 1n) === 1n) {
      shift += operations[i];
    }
  }
  return String.fromCharCode('a'.charCodeAt(0) + (shift % 26));
};

Comments