Find the K th Character in String Game II

The intuition is, to have constraints as large as 1 <= k <= 10^14, there has to be some pattern that exists allowing us to retrieve the kth character quickly.

You can see this come up in the example listed below, where you have input:

• k = 10
• operations = [1, 0]

After 4 operations, we have this:

a|b|a|b|b|c|b|c|a|b| a| b| b| c| b| c
0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15

where the numbers below denote the letters respective index.

While looking at the letters and their respective index, a pattern begins to reveal itself. Take index 11 as an example:

• index 11 came from index 3 after operation 0

a|b|a|*b*|b|c|b|c -> a|b| a|* b*| b| c| b| c
0|1|2|*3*|4|5|6|7 -> 8|9|10|*11*|12|13|14|15

• index 3 came from index 1 after operation 0

a|*b* -> a|*b*
0|*1* -> 2|*3*

• index 1 came from index 0 after operation 1

*a* -> *b*
*0* -> *1*

If we write 11 into binary, 0b1011, and relate the position of each 1 to an operation, for example:

• 0b1011 & 0b0001 = 0b0001 so the 11th digit gets operation[0 % 2] = 1
• 0b1011 & 0b0010 = 0b0010 so the 11th digit gets operation[1 % 2] = 0
• 0b1011 & 0b0100 = 0b0100 so the 11th digit does not get operation[2 % 2] = 1
• 0b1011 & 0b1000 = 0b1000 so the 11th digit gets operation[3 % 2] = 0 which mirrors the operations and the order of the operations the kth digit was placed through.

TLDR:

After n operations, word will be of length 2^n. We know that the:

• first 2^(n-1) characters was not affected by the nth operation
• last 2^(n-1) characters was the result of the nth operation on the first 2^(n-1) characters

Given their respective indices:

• the first 2^(n-1) characters will have the nth bit set to 0
• the last 2^(n-1) characters will have the nth bit set to 1

Using an inductive proof, we can show that the nth bit being set to 1 means that the respective operation has been done on the kth character.

code

class Solution {
public:
    char kthCharacter(long long k, vector<int>& operations) {
        char ans = 'a';
        int index = 0;
        k -= 1;
        while (k > 0) {
            if (k % 2 == 1 && operations[index] == 1) {
                if (ans-'a' == 25) {
                    ans = 'a';
                } else {
                    ans = ans+1;
                }
            }
            index = (index + 1) % operations.size();
            k >>= 1;
        }
        return ans;
    }
};

complexity

• Time: O(log(k)) where k is just the input k
• Space: O(1)

time taken

• 10 minutes and 30 seconds
  • from now on, I am going to time EVERYTHING (no exceptions)