algoadvance

Leetcode 1486. XOR Operation in an Array

Problem Statement

The problem “1486. XOR Operation in an Array” is described as follows:

Given an integer n and an integer start. You need to construct an array nums where nums[i] = start + 2 * i (0-indexed) and n is the size of the array. Return the bitwise XOR of all elements of the array.

Clarifying Questions

  1. Input domain: Are n and start guaranteed to be non-negative integers?
  2. Output requirements: Should the function return the XOR operation performed on all elements of the array as an integer?
  3. Constraints:
    • 1 <= n <= 1000
    • 0 <= start <= 1000
    • These constraints indicate that an O(n) solution is feasible.

Strategy

  1. Array Construction: Generate the array nums using the formula nums[i] = start + 2 * i.
  2. XOR Calculation: Initialize a variable xor_result to 0, and then iterate through the nums array to continually XOR each element with xor_result.
  3. Efficiency: Both the array construction and XOR operation can be done in a single pass through the array, making this an O(n) solution.

Code

#include <iostream>

class Solution {
public:
    int xorOperation(int n, int start) {
        int xor_result = 0;
        for(int i = 0; i < n; ++i) {
            xor_result ^= (start + 2 * i);
        }
        return xor_result;
    }
};

int main() {
    Solution solution;
    std::cout << solution.xorOperation(5, 0) << std::endl;  // Output: 8
    std::cout << solution.xorOperation(4, 3) << std::endl;  // Output: 8
    std::cout << solution.xorOperation(1, 7) << std::endl;  // Output: 7
    std::cout << solution.xorOperation(10, 5) << std::endl; // Output: 2
    return 0;
}

Time Complexity

The time complexity of this solution is O(n), where n is the size of the array. This is because we iterate through the array once to compute the XOR of all elements.

The space complexity is O(1) as we are not using any extra space that scales with input size, other than a few integer variables.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI