Leetcode — 1486. XOR Operation in an Array

It’s an easy problem with description being:

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 1:

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.
Where "^" corresponds to bitwise XOR operator.

Example 2:

Input: n = 4, start = 3
Output: 8
Explanation: Array nums is equal to [3, 5, 7, 9] where (3 ^ 5 ^ 7 ^ 9) = 8.

Constraints:

1 <= n <= 1000

0 <= start <= 1000

n == nums.length

First, to get this sorted out, you need to understand what XOR operator means.

This operator means exclusivity, meaning if both have same values, they will not get counted, if not then they will.

In this case with numbers it goes bitwise (binary numeral), so you update numbers from let’s say 9 to 1001 and use the binaries, on each, to determine if they are exclusive from one number to the other.

One example would be:

• 9 being 1001
• 8 being 1000

It shows just one exclusive number there, the first one (1 for 9 and 0 for 8), and due to that 8 ^ 9 = 1

So getting back into your problem, for us to return the bitwise XOR of all elements of nums you basically have to iterate based on n and use XOR on a sum, for each iteration, with the code being:

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

Runtime: 1ms, faster than 100.00% of Java online submissions.

Memory Usage: 40.04 MB, less than 95.84% of Java online submissions.

—

That’s it! If there is anything thing else to discuss feel free to drop a comment, if I missed anything let me know so I can update accordingly.

Until next post! :)

Comments

[Andrey Rusev]

Uhm... I'm not sure if I get this right... but why not do something like this:

int bitwiseXor = 0;
int end = start + 2 * n; // compute only once instead of once per loop
for (int cn = start; cn < end; cn += 2) {
    bitwiseXor ^= cn;
}

Or in other words - you should be able to save some arithmetic operations (like the multiplying i * 2 and also adding start every time)?