DEV Community

Cover image for 2683. Neighboring Bitwise XOR
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on

2683. Neighboring Bitwise XOR

2683. Neighboring Bitwise XOR

Difficulty: Medium

Topics: Array, Bit Manipulation

A 0-indexed array derived with length n is derived by computing the bitwise XOR (⊕) of adjacent values in a binary array original of length n.

Specifically, for each index i in the range [0, n - 1]:

  • If i = n - 1, then derived[i] = original[i] ⊕ original[0].
  • Otherwise, derived[i] = original[i] ⊕ original[i + 1].

Given an array derived, your task is to determine whether there exists a valid binary array original that could have formed derived.

Return true if such an array exists or false otherwise.

  • A binary array is an array containing only 0's and 1's

Example 1:

  • Input: derived = [1,1,0]
  • Output: true
  • Explanation: A valid original array that gives derived is [0,1,0].
    • derived[0] = original[0] ⊕ original[1] = 0 ⊕ 1 = 1
    • derived[1] = original[1] ⊕ original[2] = 1 ⊕ 0 = 1
    • derived[2] = original[2] ⊕ original[0] = 0 ⊕ 0 = 0

Example 2:

  • Input: derived = [1,1]
  • Output: true
  • Explanation: A valid original array that gives derived is [0,1].
    • derived[0] = original[0] ⊕ original[1] = 1
    • derived[1] = original[1] ⊕ original[0] = 1

Example 3:

  • Input: derived = [1,0]
  • Output: false
  • Explanation: There is no valid original array that gives derived.

Constraints:

  • n == derived.length
  • 1 <= n <= 105
  • The values in derived are either 0's or 1's

Hint:

  1. Understand that from the original element, we are using each element twice to construct the derived array
  2. The xor-sum of the derived array should be 0 since there is always a duplicate occurrence of each element.

Solution:

To determine whether a valid binary array original exists that could form the given derived array, we can use the properties of XOR:

Key Observations:

  1. Each derived[i] is the XOR of two adjacent elements in original:

    • For i = n - 1, derived[i] = original[n-1] ⊕ original[0].
    • Otherwise, derived[i] = original[i] ⊕ original[i+1].
  2. XOR properties:

    • a ⊕ a = 0 (XOR of a number with itself is 0).
    • a ⊕ 0 = a (XOR of a number with 0 is the number itself).
    • XOR is commutative and associative.
  3. To construct a valid original, the XOR of all elements in derived must equal 0. Why? Because for a circular XOR relationship to work (start and end wrap back to the beginning), the cumulative XOR of derived should cancel out.

Steps:

  1. Compute the XOR of all elements in derived.
  2. If the result is 0, a valid original exists; otherwise, it does not.

Algorithm:

  • Compute the XOR of all elements in derived.
  • If the XOR is 0, return true.
  • Otherwise, return false.

Let's implement this solution in PHP: 2683. Neighboring Bitwise XOR

<?php
/**
 * @param Integer[] $derived
 * @return Boolean
 */
function doesValidArrayExist($derived) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$derived1 = [1, 1, 0];
echo doesValidArrayExist($derived1) ? 'true' : 'false'; // Output: true

// Example 2
$derived2 = [1, 1];
echo doesValidArrayExist($derived2) ? 'true' : 'false'; // Output: true

// Example 3
$derived3 = [1, 0];
echo doesValidArrayExist($derived3) ? 'true' : 'false'; // Output: false
?>
Enter fullscreen mode Exit fullscreen mode

Explanation:

  1. We initialize $xorSum to 0.
  2. For each element in derived, we XOR it with $xorSum.
  3. At the end of the loop, $xorSum will contain the XOR of all elements in derived.
  4. If $xorSum is 0, return true; otherwise, return false.

Complexity:

  • Time Complexity: O(n), where n is the length of derived. We only iterate through the array once.
  • Space Complexity: O(1), as we only use a single variable to compute the XOR.

This approach efficiently checks for the existence of a valid original array within the given constraints.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay