Given a binary representation in the form of string(S) of a number n, the task is to find a binary representation of n-1.
Note: n is greater than zero. 
Example 1:
Input: S = "11"
Output: 10
Explanation: "11" is the binary 
representation of 3 and binary 
representation of 2 is "10"
Example 1:
Input: S = "1000"
Output: 111
Explanation: "1000" is the binary 
representation of 8 and binary 
representation of 7 is "111"
Your Task:  
You don't need to read input or print anything. Complete the function binaryPreviousNumber() which takes S as input parameter and returns the string.
Expected Time Complexity:O(N)
Expected Auxiliary Space: O(N) to store resultant string  
Constraints:
1 <= N <= 10^{4}

Difficulty: EASY
Tags: Bit manipulation

Data structures
Skill types: Bit manipulation

Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N) to store resultant string

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

Solutions:
class Solution:

	def binaryPreviousNumber(self, S):
		n = int(S, 2)
		n = n - 1
		stri = bin(n)[2:]
		return stri


class Solution:

	def binaryPreviousNumber(self, S):
		x = int(S, 2)
		return bin(x - 1)[2:]


class Solution:

	def binaryPreviousNumber(self, S):
		for i in range(len(S) - 1, -1, -1):
			if S[i] == '1':
				break
		res = ''
		for j in range(len(S)):
			if j >= i:
				if j == i:
					res += '0'
				else:
					res += '1'
			else:
				res += S[j]
		for i in range(len(res)):
			if res[i] == '1':
				break
		res = res[i:]
		return res


class Solution:

	def binaryPreviousNumber(self, s):
		k = int(s, 2)
		n = k - 1
		m = bin(n)
		return m[2:]


class Solution:

	def binaryPreviousNumber(self, S):
		a = int(S, 2) - 1
		c = bin(a)
		b = str(c)
		return b[2:]


class Solution:

	def binaryPreviousNumber(self, S):
		return bin(eval('0b' + S) - 1)[2:]


class Solution:

	def binaryPreviousNumber(self, S):
		S = bin(int(S, 2) - 1).replace('0b', '')
		return S


class Solution:

	def binaryPreviousNumber(self, S):
		num = int(S, 2)
		return bin(num - 1)[2:]


class Solution:

	def binaryPreviousNumber(self, S):
		l = []
		flag = False
		for i in S:
			if i == '1':
				flag = True
			if flag:
				l.append(i)
		if len(l) == 0:
			return 0
		n = len(l)
		if n == 1 and l[0] == '1':
			return '0'
		for i in range(len(l) - 1, -1, -1):
			if l[i] == '1':
				l[i] = '0'
				break
			else:
				l[i] = '1'
		flag = False
		l1 = []
		for i in l:
			if i == '1':
				flag = True
			if flag:
				l1.append(i)
		if len(l1) == 0:
			l1 = ['1'] * n
		return ''.join(l1)


class Solution:

	def binaryPreviousNumber(self, S):
		S = S.lstrip('0')
		if S == '1':
			return '0'
		n = len(S)
		b = (n - 1) * '1' + '0'
		t = ''
		c = '0'
		s = {'000': '00', '001': '10', '010': '10', '011': '01', '100': '10', '101': '01', '110': '01', '111': '11'}
		for i in range(n - 1, -1, -1):
			g = S[i] + b[i] + c
			t += s[g][0]
			c = s[g][1]
		t = t[::-1]
		y = ''
		for i in range(n - 1, -1, -1):
			g = t[i] + '0' + c
			y += s[g][0]
			c = s[g][1]
		y = y[::-1]
		y = y.lstrip('0')
		return y


class Solution:

	def binaryPreviousNumber(self, S):
		x = int(S, 2)
		return bin(x - 1)[2:]
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		S = input()
		ob = Solution()
		ans = ob.binaryPreviousNumber(S)
		print(ans)


class Solution:

	def binaryPreviousNumber(self, S):
		z = int(S, 2)
		return bin(z - 1)[2:]


class Solution:

	def binaryPreviousNumber(self, s):
		s = self.removeLeadingZeros(s)
		siz = len(s)
		if s[siz - 1] == '1':
			return s[0:siz - 1] + '0'
		countZero = 0
		previousBit = None
		binaryStr = ''
		hasFoundConsecutiveZeros = False
		for i in reversed(range(siz)):
			currentBit = s[i]
			if currentBit == '0':
				countZero += 1
			if previousBit == None:
				binaryStr = '1'
			elif hasFoundConsecutiveZeros == False:
				if previousBit != currentBit:
					hasFoundConsecutiveZeros = True
					binaryStr = '0' + binaryStr
				else:
					binaryStr = '1' + binaryStr
			else:
				binaryStr = currentBit + binaryStr
			previousBit = currentBit
		if countZero == siz - 1:
			return self.generateStr(siz - 1, '1')
		return binaryStr

	def removeLeadingZeros(self, s):
		if s[0] == '1':
			return s
		index = 0
		for i in range(len(s)):
			if s[i] == '1':
				index = i
				return s[index:]
		return '0'

	def generateStr(self, n, c):
		result = ''
		for i in range(n):
			result += c
		return result


class Solution:

	def binaryPreviousNumber(self, a):
		a = self.removeLeadingZeros(a)
		result = self.subtractOne(a)
		return self.removeLeadingZeros(result)

	def removeLeadingZeros(self, s):
		if s[0] != '0':
			return s
		index = 0
		for i in range(len(s)):
			if s[i] == '1':
				index = i
				break
		return s[index:]

	def subtractOne(self, a):
		siz = len(a)
		b = '1'.zfill(siz)
		carry = None
		result = ''
		for i in reversed(range(siz)):
			(bitDiff, carry) = self.subtractBit(int(a[i]), int(b[i]), carry)
			result = str(bitDiff) + result
		return result

	def subtractBit(self, a, b, carry):
		result = 0
		if carry == None:
			result = a ^ b
		else:
			result = a ^ b ^ carry
		if a == 0 and (b == 1 or carry == 1):
			carry = 1
		else:
			carry = None
		return (result, carry)


class Solution:

	def binaryPreviousNumber(self, S):
		S = list(S)
		for i in range(len(S) - 1, -1, -1):
			if S[i] == '1':
				S[i] = '0'
				break
			else:
				S[i] = '1'
		for i in range(len(S)):
			if S[i] == '1':
				indx = i
				break
		return ''.join(S[i:])


class Solution:

	def binaryPreviousNumber(self, S):
		num = int(S, 2)
		res = num - 1
		if res == 0:
			return '0'
		str_res = ''
		while res != 0:
			if res & 1 == 1:
				str_res = '1' + str_res
			else:
				str_res = '0' + str_res
			res = res >> 1
		return str_res


class Solution:

	def binaryPreviousNumber(self, S):
		a = int(S, 2) - 1
		res = bin(a)[2:]
		return res


class Solution:

	def binaryPreviousNumber(self, S):
		k = int(S, 2)
		m = k - 1
		return bin(m)[2:]