algoadvance

Leetcode 1486. XOR Operation in an Array

Problem Statement

You are given an integer n and an integer start.

Define an array nums where nums[i] = start + 2 * i (0-indexed) and n == nums.length.

Return the bitwise XOR of all elements of nums.

Example:

Input: n = 5, start = 0
Output: 8
Explanation: Array nums is equal to [0, 2, 4, 6, 8] where (0^2^4^6^8) = 8.

Clarifying Questions

1. Is n always a positive integer?
   • Yes, assume n is always a positive integer.
2. What are the constraints on n and start?
   • Typically constraints in such problems range from small values up to the order of thousand or more. For this problem, we assume 1 <= n <= 1000 and 0 <= start <= 1000.
3. Can n be zero?
   • The problem constraints likely guarantee n is at least 1 since arrays of size 0 wouldn’t produce meaningful XOR results.

Strategy

The strategy is straightforward:

1. Construct the array nums using the formula nums[i] = start + 2 * i.
2. Iterate through the array and compute the XOR of all elements.

Code

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.xorOperation(5, 0)); // Output: 8
        System.out.println(sol.xorOperation(4, 3)); // Output: 8
        System.out.println(sol.xorOperation(1, 7)); // Output: 7
        System.out.println(sol.xorOperation(10, 5)); // Output: 2
    }
}

Time Complexity

• Time Complexity: O(n), iterating through the array of size n once.
• Space Complexity: O(1), the space used is constant as we only use a single integer to store the XOR result. We don’t store the nums array explicitly.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?