문제 링크

• 아이디어가 빨리 떠올랐다..

내 코드

• 0ms, 99.69MB

class Solution {
public:
    vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {
        int xorNum{};
        for(int num : nums) {
            xorNum ^= num;
        }
        
        vector<int> answer;
        int maximumNum = (1 << maximumBit) - 1;
        for(auto it{rbegin(nums)};it!=rend(nums);++it) {
            answer.push_back(maximumNum ^ xorNum);
            xorNum ^= *it;
        }

        return answer;
    }
};

Solution

Approach 1: Prefix Array + Bit Masking

• 0ms, 98.32MB
• Complexity
  • Time Complexity: $O(n)$
  • Space Complexity: $O(n)$

class Solution {
public:
    vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {
        int n = nums.size();

        vector<int> prefixXOR(n);
        prefixXOR[0] = nums[0];

        for (int i = 1; i < n; i++) {
            prefixXOR[i] = prefixXOR[i - 1] ^ nums[i];
        }

        vector<int> ans(n);
        int mask = (1 << maximumBit) - 1;

        for (int i = 0; i < n; i++) {
            // find k to maximize value
            int currentXOR = prefixXOR[n - 1 - i];
            ans[i] = currentXOR ^ mask;
        }

        return ans;
    }
};

Approach 2: Optimized Calculation + Bit Masking

• 0ms, 95.37MB
• Complexity
  • Time Complexity: $O(n)$
  • Space Complexity: $O(1)$

class Solution {
public:
    vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {
        int xorProduct = 0;
        for (int i = 0; i < nums.size(); i++) {
            xorProduct = xorProduct ^ nums[i];
        }
        vector<int> ans(nums.size());

        int mask = (1 << maximumBit) - 1;

        for (int i = 0; i < nums.size(); i++) {
            ans[i] = xorProduct ^ mask;
            // remove last element
            xorProduct = xorProduct ^ nums[nums.size() - 1 - i];
        }

        return ans;
    }
};