{"id":8361,"date":"2021-04-17T12:08:24","date_gmt":"2021-04-17T19:08:24","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8361"},"modified":"2021-04-17T12:32:14","modified_gmt":"2021-04-17T19:32:14","slug":"leetcode-1829-maximum-xor-for-each-query","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/bit\/leetcode-1829-maximum-xor-for-each-query\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1829. Maximum XOR for Each Query"},"content":{"rendered":"\n

You are given a sorted<\/strong> array nums<\/code> of n<\/code> non-negative integers and an integer maximumBit<\/code>. You want to perform the following query n<\/code> times<\/strong>:<\/p>\n\n\n\n

  1. Find a non-negative integer k < 2maximumBit<\/sup><\/code> such that nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k<\/code> is maximized<\/strong>. k<\/code> is the answer to the ith<\/sup><\/code> query.<\/li>
  2. Remove the last <\/strong>element from the current array nums<\/code>.<\/li><\/ol>\n\n\n\n

    Return an array<\/em> answer<\/code>, where <\/em>answer[i]<\/code> is the answer to the <\/em>ith<\/sup><\/code> query<\/em>.<\/p>\n\n\n\n

    Example 1:<\/strong><\/p>\n\n\n\n

    Input:<\/strong> nums = [0,1,1,3], maximumBit = 2\nOutput:<\/strong> [0,3,2,3]\nExplanation<\/strong>: The queries are answered as follows:\n1st<\/sup> query: nums = [0,1,1,3], k = 0 since 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3.\n2nd<\/sup> query: nums = [0,1,1], k = 3 since 0 XOR 1 XOR 1 XOR 3 = 3.\n3rd<\/sup> query: nums = [0,1], k = 2 since 0 XOR 1 XOR 2 = 3.\n4th<\/sup> query: nums = [0], k = 3 since 0 XOR 3 = 3.\n<\/pre>\n\n\n\n
    Example 2:<\/strong><\/p>\n\n\n\n
    Input:<\/strong> nums = [2,3,4,7], maximumBit = 3\nOutput:<\/strong> [5,2,6,5]\nExplanation<\/strong>: The queries are answered as follows:\n1st<\/sup> query: nums = [2,3,4,7], k = 5 since 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7.\n2nd<\/sup> query: nums = [2,3,4], k = 2 since 2 XOR 3 XOR 4 XOR 2 = 7.\n3rd<\/sup> query: nums = [2,3], k = 6 since 2 XOR 3 XOR 6 = 7.\n4th<\/sup> query: nums = [2], k = 5 since 2 XOR 5 = 7.\n<\/pre>\n\n\n\n
    Example 3:<\/strong><\/p>\n\n\n\n
    Input:<\/strong> nums = [0,1,2,2,5,7], maximumBit = 3\nOutput:<\/strong> [4,3,6,4,6,7]\n<\/pre>\n\n\n\n
    Constraints:<\/strong><\/p>\n\n\n\n
    • nums.length == n<\/code><\/li>
    • 1 <= n <= 105<\/sup><\/code><\/li>
    • 1 <= maximumBit <= 20<\/code><\/li>
    • 0 <= nums[i] < 2maximumBit<\/sup><\/code><\/li>
    • nums<\/code>\u200b\u200b\u200b is sorted in ascending<\/strong> order.<\/li><\/ul>\n\n\n\n
      Solution: Prefix XOR<\/strong><\/h2>\n\n\n\n
      Compute s = nums[0] ^ nums[1] ^ … nums[n-1] first<\/p>\n\n\n\n
      to remove nums[i], we just need to do s ^= nums[i]<\/p>\n\n\n\n
      We can always maximize the xor of s and k to (2^maxbit – 1)
      k = (2 ^ maxbit – 1) ^ s<\/p>\n\n\n\n
      Time complexity: O(n)
      Space complexity: O(1)<\/p>\n\n\n\n
      \n
      C++<\/h2>\n
      \n\n
      \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector getMaximumXor(vector& nums, int maximumBit) {\n    const int t = (1 << maximumBit) - 1;\n    const int n = nums.size();\n    vector ans(n);\n    int s = 0;\n    for (int x : nums) s ^= x;    \n    for (int i = n - 1; i >= 0; --i) {\n      ans[n - i - 1] = t ^ s;\n      s ^= nums[i];\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
      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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[126],"tags":[16,177,97,63],"class_list":["post-8361","post","type-post","status-publish","format-standard","hentry","category-bit","tag-bit","tag-medium","tag-prefix","tag-xor","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8361","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8361"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8361\/revisions"}],"predecessor-version":[{"id":8365,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8361\/revisions\/8365"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8361"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8361"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8361"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}