2025-07-03 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's July LeetCoding Challenge with cpp.

July LeetCoding Challenge 3

Description

Find the K-th Character in String Game I

Alice and Bob are playing a game. Initially, Alice has a string word = "a".

You are given a positive integer k.

Now Bob will ask Alice to perform the following operation forever:

  • Generate a new string by changing each character in word to its next character in the English alphabet, and append it to the original word.

For example, performing the operation on "c" generates "cd" and performing the operation on "zb" generates "zbac".

Return the value of the kth character in word, after enough operations have been done for word to have at least k characters.

Note that the character 'z' can be changed to 'a' in the operation.

 

Example 1:

Input: k = 5

Output: "b"

Explanation:

Initially, word = "a". We need to do the operation three times:

  • Generated string is "b", word becomes "ab".
  • Generated string is "bc", word becomes "abbc".
  • Generated string is "bccd", word becomes "abbcbccd".

Example 2:

Input: k = 10

Output: "c"

 

Constraints:

  • 1 <= k <= 500

Solution

class Solution {
public:
  char kthCharacter(int k) {
    char result = 0;
    int base = 1;
    int exp = 0;
    for(; base < k ; base *= 2) {
      base *= 2;
    }
    base /= 2;
    while(base) {
      if(k > base) {
        k -= base;
        result += 1;
        result %= 26;
      }
      base /= 2;
    }
    return result + 'a';
  }
};

// Accepted
// 502/502 cases passed (0 ms)
// Your runtime beats 100 % of cpp submissions
// Your memory usage beats 100 % of cpp submissions (7.6 MB)

then I found that it's actually the sum of the count of lower zero bits and count of one bits minus one.

class Solution {
public:
  char kthCharacter(int k) {
    return __builtin_popcount(k) + __builtin_ffs(k) - 2 + 'a';
  }
};

// Accepted
// 502/502 cases passed (0 ms)
// Your runtime beats 100 % of cpp submissions
// Your memory usage beats 100 % of cpp submissions (7.6 MB)
Algorithm