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}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Mathematics

Starter code: #User function Template for python3
class Solution:
    def posInfinite (self, pos):
        # code here 

Solutions:
class Solution:

	def posInfinite(self, pos):
		A = '12345'

		def find_iter(pos):
			n = 10 ** 3
			length = 5
			iteration = 0
			for i in range(1, n):
				length = 2 * length + i
				if length > pos:
					iteration = i
					break
			return (iteration, length)

		def func(length, iteration, pos):
			if pos <= 5:
				return A[pos - 1]
			part_length = (length - iteration) // 2
			(left, mid, right) = (part_length, iteration, part_length)
			if pos <= left:
				pass
			elif pos <= left + mid:
				return '$'
			else:
				pos = pos - (left + mid)
				pos = left - pos + 1
			return func(left, iteration - 1, pos)
		(iteration, length) = find_iter(pos)
		res1 = func(length, iteration, pos)
		return res1


class Solution:

	def find_(self, pos, li):
		if pos <= 11:
			if pos <= 5:
				return str(pos)
			elif pos == 6:
				return '$'
			elif pos > 6:
				return str(11 - pos + 1)
		l = len(li)
		brp = 0
		for i in range(l):
			if li[i] <= pos and li[i + 1] >= pos:
				brp = i
				break
		if li[brp] + brp + 1 >= pos:
			return '$'
		else:
			return self.find_(pos - (li[brp] + brp + 1), li)

	def posInfinite(self, pos):
		li = [5]
		num = 5
		for i in range(1, 41):
			num = num * 2 + i
			li.append(num)
		return self.find_(pos, li)


class Solution:

	def posInfinite(self, pos):
		r = '12345'
		n = len(r)
		f = [n]
		lim = 10 ** 12
		while f[-1] * 2 + len(f) <= lim:
			f.append(f[-1] * 2 + len(f))

		def get(N, K):
			if N == 0:
				return r[K - 1]
			if K > f[N - 1] + N:
				return get(N - 1, f[N - 1] - (K - f[N - 1] - N) + 1)
			if K > f[N - 1]:
				return '$'
			return get(N - 1, K)
		return get(len(f) - 1, pos)


class Solution:

	def posInfinite(self, pos):
		r = '12345'
		n = len(r)
		f = [n]
		lim = 10 ** 12
		while f[-1] * 2 + len(f) <= lim:
			f.append(f[-1] * 2 + len(f))

		def get(N, K):
			if N == 0:
				return r[K - 1]
			if K > f[N - 1] + N:
				return get(N - 1, f[N - 1] - (K - f[N - 1] - N) + 1)
			if K > f[N - 1]:
				return '$'
			return get(N - 1, K)
		for _ in range(1):
			k = pos
			ans = ''
			for i in range(len(f)):
				if f[i] >= k:
					ans = get(i, k)
					break
			return ans


class Solution:

	def posInfinite(self, q):
		g_str = ['1', '2', '3', '4', '5', '$', '5', '4', '3', '2', '1']
		while q > len(g_str):
			(m, itr) = self.GetValues(q)
			val = int((m - itr) / 2 + itr)
			if q <= val:
				q = 6
				break
			q -= val
		if q > 0:
			return g_str[q - 1]
		return ''

	def GetValues(self, q):
		size = 5
		itr = 0
		while True:
			if q <= size:
				return (size, itr)
			itr += 1
			size = size * 2 + itr