1829. Maximum XOR for Each Query

1829. Maximum XOR for Each Query
Solved
Medium
Topics
Companies
Hint
You are given a sorted array nums of n non-negative integers and an integer maximumBit. You want to perform the following query n times:

Find a non-negative integer k < 2maximumBit such that nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k is maximized. k is the answer to the ith query.
Remove the last element from the current array nums.
Return an array answer, where answer[i] is the answer to the ith query.

---

접근

 

n 개의 주어진 숫자에서 XOR 결과가 가장 큰 값이 되는 k 를 찾습니다.

가장 큰 값은 주어진 파라미터 maximumBit 을 따라  2 ^ max_bit 입니다.

nums 에서 i 번째 값까지 각 숫자의 bit 자리수가 홀수로 만드는 bit 를 찾고 이를 10 진수로 변환하면 k 를 얻을 수 있습니다.

 

처음에는 매 회차 ( i ) 를 계산하여 k 를 얻으면 n^3 이 발생하여 "time exceeded" 가 발생합니다.

모든 bit 를 더한 값에 회차 ( i ) 의 bit 를 빼면서 k 값을 계산하여 n^2 를 사용합니다.

---

코드

/**
 * @param {number[]} nums
 * @param {number} maximumBit
 * @return {number[]}
 */
var getMaximumXor = function (nums, maximumBit) {
    var bits = [];
    var sums = [];
    for (var j = 0; j < maximumBit; j++) {
        sums[j] = 0;
    }

    for (var i = 0; i < nums.length; i++) {
        var e = nums[i];
        var j = 0;

        var bit = [];
        while (e > 0) {
            var v = e % 2 == 1 ? 1 : 0;
            bit.push(v);
            e = e >> 1;

            sums[j] += v;

            j++;
        }
        bits.push(bit);
    }

    var answer = [];

    for (var i = nums.length; i > 0; i--) {
        var r = 0;
        var t = 1;
        for (var j = 0; j < maximumBit; j++) {
            if (sums[j] % 2 == 0) {
                r += t;
            }

            t = t << 1;
        }

        answer.push(r);

        for (var j = 0; j < maximumBit; j++) {
            sums[j] -= bits[i - 1][j] || 0;
        }
    }

    return answer;
};