크기가 n인 nums라고 하는 사전 정렬된 배열이 있고 하나의 값 b도 있다고 가정합니다. 다음 쿼리를 n번 수행하려고 합니다. -
-
nums 및 k에 있는 모든 요소의 XOR이 최대화되도록 음이 아닌 값 k <2^m을 검색합니다. 따라서 k는 i번째 쿼리에 대한 답변입니다.
-
현재 배열 nums에서 마지막 요소를 제거합니다.
-
배열 답변을 찾아야 합니다. 여기서 answer[i]는 i번째 쿼리에 대한 답변입니다.
따라서 입력이 nums =[0,1,1,3], m =2와 같으면 출력은 [0,3,2,3]이 됩니다. 왜냐하면
-
nums =[0,1,1,3], k =0 이후 0 XOR 1 XOR 1 XOR 3 XOR 0 =3.
-
nums =[0,1,1], k =3 이후 0 XOR 1 XOR 1 XOR 3 =3.
-
nums =[0,1], k =2 이후 0 XOR 1 XOR 2 =3.
-
nums =[0], k =3, 0 XOR 3 =3.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
x :=2^m - 1
-
범위 0에서 숫자 - 1까지의 i에 대해 수행
-
nums[i] :=nums[i] XOR x
-
x :=숫자[i]
-
-
반전 후 숫자 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(nums, m):
x=2**m-1
for i in range(len(nums)):
nums[i]^= x
x = nums[i]
return(nums[::-1])
nums = [0,1,1,3]
m = 2
print(solve(nums, m))
입력
[0,1,1,3], 2
출력
[0, 3, 2, 3]