Consider a string A = "12345". An infinite string is built by performing infinite steps on A recursively. In i^{th} step, A is concatenated with ‘$’ i times followed by reverse of A, that is, A = A | $...$ | reverse(A), where | denotes concatenation.
Given a position pos, find out the character at pos in the infinite string.
Example 1:
Input: pos = 3
Output: 3
Explanation: A = "12345", then A[pos] is 3.
Example 2:
Input: pos = 10
Output: 2
Explanation: A = "12345$54321", then A[pos] is 2.
Your Task:
You dont need to read input or print anything. Complete the function posInfinite() which takes pos as input parameter and returns the character in the infinite string at pos.
Expected Time Complexity: O(sqrtn)
Expected Auxiliary Space: O(1)
Constraints:
1<= pos <=10^{12}

见题面

见题面