



'''simple docstring'''

def 				a  (     UpperCamelCase_    :    str			)       ->	Any:
		if not head:
				return True
		# split the list to two parts
		snake_case__     ,	snake_case__	     =head.next, head
		while fast and fast.next:
				snake_case__	     =fast.next.next
				snake_case__	     =slow.next
		snake_case__	     =slow.next
		snake_case__	     =None  # Don't forget here! But forget still works!
		# reverse the second part
		snake_case__	     =None
		while second:
				snake_case__	     =second.next
				snake_case__	     =node
				snake_case__	     =second
				snake_case__	     =nxt
		# compare two parts
		# second part has the same or one less node
		while node:
				if node.val != head.val:
						return False
				snake_case__	     =node.next
				snake_case__	     =head.next
		return True






def 				a  (     UpperCamelCase_    :    List[str]			)       ->	List[Any]:
		if not head or not head.next:
				return True

		# 1. Get the midpoint (slow)
		snake_case__	     =snake_case__	     =snake_case__	     =head
		while fast and fast.next:
				snake_case__     ,	snake_case__	     =fast.next.next, slow.next

		# 2. Push the second half into the stack
		snake_case__	     =[slow.val]
		while slow.next:
				snake_case__	     =slow.next
				stack.append(slow.val			)

		# 3. Comparison
		while stack:
				if stack.pop() != cur.val:
						return False
				snake_case__	     =cur.next

		return True






def 				a  (     UpperCamelCase_    :    List[str]			)       ->	List[str]:
		if not head or not head.next:
				return True
		snake_case__	     ={}
		snake_case__	     =0
		while head:
				if head.val in d:
						d[head.val].append(UpperCamelCase_			)
				else:
						snake_case__	     =[pos]
				snake_case__	     =head.next
				pos += 1
		snake_case__	     =pos - 1
		snake_case__	     =0
		for v in d.values():
				if len(UpperCamelCase_			) % 2 != 0:
						middle += 1
				else:
						snake_case__	     =0
						for i in range(0      ,					len(UpperCamelCase_			)			):
								if v[i] + v[len(UpperCamelCase_			) - 1 - step] != checksum:
										return False
								step += 1
				if middle > 1:
						return False
		return True









'''simple docstring'''

from timeit import timeit






def 				a  (     UpperCamelCase_    :    int			)       ->	int:
		if number < 0:
				raise ValueError('the value of input must not be negative'			)
		snake_case__	     =0
		while number:
				number &= number - 1
				result += 1
		return result






def 				a  (     UpperCamelCase_    :    int			)       ->	int:
		if number < 0:
				raise ValueError('the value of input must not be negative'			)
		snake_case__	     =0
		while number:
				if number % 2 == 1:
						result += 1
				number >>= 1
		return result






def 				a  (     )       ->	None:

		def do_benchmark(UpperCamelCase_    :    int			) -> None:
				snake_case__	     ='import __main__ as z'
				print(f"""Benchmark when {number = }:"""			)
				print(f"""{get_set_bits_count_using_modulo_operator(UpperCamelCase_			) = }"""			)
				snake_case__	     =timeit('z.get_set_bits_count_using_modulo_operator(25)'      ,					setup=UpperCamelCase_			)
				print(f"""timeit() runs in {timing} seconds"""			)
				print(f"""{get_set_bits_count_using_brian_kernighans_algorithm(UpperCamelCase_			) = }"""			)
				snake_case__	     =timeit(
				    'z.get_set_bits_count_using_brian_kernighans_algorithm(25)'      ,					setup=UpperCamelCase_      ,					)
				print(f"""timeit() runs in {timing} seconds"""			)

		for number in (25, 37, 58, 0):
				do_benchmark(UpperCamelCase_			)
				print()


if __name__ == "__main__":
			import doctest

			doctest.testmod()
			benchmark()




