K-th Character After String Operations - Teradata Online Assessment IIT R

Problem Preview

"Initially, a string `s` contains only one character: ```text s = "a" ``` You are given a vector `ops` containing only `0` and `1`. For every operation, the current string is transformed and appended to itself. There are two types of operations: ### Operation 0 Duplicate the current string and append the duplicate **unchanged** to the end. For example: ```text s = "abc" ``` After operation `0`: ```text s = "abcabc" ``` ### Operation 1 Duplicate the current string, increment every character in the duplicate by `1`, and append it to the original string. Characters are incremented cyclically: ```text a → b b → c ... y → z z → a ``` For example: ```text s = "abc" ``` After operation `1`: ```text s = "abcbcd" ``` You are given: * A vector `ops` containing the operations to perform. * An integer `k` representing a **1-indexed position** in the final string. After performing all operations in `ops`, return the character present at position `k`. ### Input Format * The first line contains an integer `N`, the number of operations. * The second line contains `N` integers, where each integer is either `0` or `1`. * The third line contains an integer `k`. ### Output Format Print the character at the `k`-th position of the final string. ### Example 1 #### Input ```text 3 0 1 0 5 ``` #### Operations Initially: ```text "a" ``` After operation `0`: ```text "aa" ``` After operation `1`: ```text "abb" ``` After operation `0`: ```text "abbabb" ``` The 5th character is: ```text b ``` #### Output ```text b ``` ### Example 2 #### Input ```text 2 1 1 4 ``` Initially: ```text "a" ``` After operation `1`: ```text "ab" ``` After operation `1`: ```text "abbc" ``` The 4th character is: ```text c ``` #### Output ```text c ``` ### Constraints * `1 ≤ N ≤ 10^5` * `ops[i] ∈ {0, 1}` * `1 ≤ k ≤ 2^N` * The final string may be exponentially large, so constructing the complete string is not feasible."