


def     UpperCamelCase_(			_A				:list					)->						list:
			UpperCamelCase__   =    len(_A					)

			# Set the gap value to be decreased by a factor of 1.3
			# after each iteration
			UpperCamelCase__   =    1.3

			# Continue sorting until the gap is 1
			while gap > 1:
						# Decrease the gap value
						UpperCamelCase__   =    int(gap / shrink					)

						# Sort the elements using insertion sort
						for i in range(_A			,       len(_A					)					):
									UpperCamelCase__   =    collection[i]
									UpperCamelCase__   =    i
									while j >= gap and collection[j - gap] > temp:
												UpperCamelCase__   =    collection[j - gap]
												j -= gap
									UpperCamelCase__   =    temp

			return collection


if __name__ == "__main__":
						import doctest

						doctest.testmod()






import qiskit
from qiskit.providers import Backend
def     UpperCamelCase_(			_A				:int			,       _A				:int					)->						tuple[qiskit.QuantumCircuit, str, str]:
			UpperCamelCase__, UpperCamelCase__   =    bin(_A					)[2:], bin(_A					)[2:]  # Remove leading '0b'

			# Ensure that both strings are of the same length
			if len(_A					) > len(_A					):
						UpperCamelCase__   =    y.zfill(len(_A					)					)
			else:
						UpperCamelCase__   =    x.zfill(len(_A					)					)

			# We need (3 * number of bits in the larger number)+1 qBits
			# The second parameter is the number of classical registers, to measure the result
			UpperCamelCase__   =    qiskit.QuantumCircuit((len(_A					) * 3) + 1			,       len(_A					) + 1					)

			# We are essentially "not-ing" the bits that are 1
			# Reversed because it's easier to perform ops on more significant bits
			for i in range(len(_A					)					):
						if x[::-1][i] == "1":
									circuit.x(_A					)
			for j in range(len(_A					)					):
						if y[::-1][j] == "1":
									circuit.x(len(_A					) + j					)

			return circuit, x, y
def     UpperCamelCase_(			_A				:qiskit.QuantumCircuit			,       _A				:int			,       _A				:int			,       _A				:int			,       _A				:int			,       )->						Union[str, Any]:
			circuit.ccx(_A			,       _A			,       _A					)
			circuit.cx(_A			,       _A					)
			circuit.ccx(_A			,       _A			,       _A					)
			circuit.cx(_A			,       _A					)
			circuit.cx(_A			,       _A					)
def     UpperCamelCase_(			_A				:int			,       _A				:int			,       _A				:Backend = qiskit.Aer.get_backend("aer_simulator"					)			,       )->						int:

			if vala < 0 or vala < 0:
						raise ValueError("Both Integers must be positive!"					)

			# Store the Integers
			UpperCamelCase__, UpperCamelCase__, UpperCamelCase__   =    store_two_classics(_A			,       _A					)
			for i in range(len(_A					)					):
						full_adder(_A			,       _A			,       len(_A					) + i			,       len(_A					) + len(_A					) + i			,       len(_A					) + len(_A					) + i + 1					)
						circuit.barrier()  # Optional, just for aesthetics

			# Measure the resultant qBits
			for i in range(len(_A					) + 1					):
						circuit.measure([(len(_A					) * 2) + i]			,       [i]					)

			UpperCamelCase__   =    qiskit.execute(_A			,       _A			,       shots=1					).result()

			# The result is in binary. Convert it back to int
			return int(list(res.get_counts()					)[0]			,       2					)


if __name__ == "__main__":
						import doctest

						doctest.testmod()


