Skip to content

Latest commit

 

History

History
70 lines (47 loc) · 2.47 KB

031.md

File metadata and controls

70 lines (47 loc) · 2.47 KB

1486. XOR Operation in an Array

Difficulty: 🟢 Easy

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.

Examples

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

Solutions

O(n) solution in Python3

class Solution:
    def xorOperation(self, n: int, start: int) -> int:
        result = start
        for i in range(1, n):
            result ^= start + 2 * i
        return result

The given solution calculates the bitwise XOR of the elements in the nums array by iteratively performing XOR operations.

The algorithm works as follows:

  1. Initialize a variable result with the value of start. This variable will store the cumulative XOR of the elements.
  2. Iterate through the range from 1 to n, representing the indices of the nums array.
    • Calculate the value of nums[i] as start + 2 * i.
    • Perform a bitwise XOR operation between result and nums[i], and update result with the XOR result.
  3. Return the value of result, which represents the bitwise XOR of all the elements in the nums array.

The algorithm calculates the XOR of each element in the nums array and updates the cumulative XOR result stored in the result variable.

Analysis of Time and Space Complexity

The time complexity of this algorithm is O(n), where n is the value of n. The algorithm iterates through the range from 1 to n and performs a constant-time XOR operation at each iteration.

The space complexity of the algorithm is O(1) as it uses only a constant amount of extra space to store the result variable.

Summary

The given solution calculates the bitwise XOR of the elements in the nums array based on the given n and start values. It has a time complexity of O(n) and a space complexity of O(1), making it an efficient solution for the problem at hand.

NB: If you want to get community points please suggest solutions in other languages as merge requests.