LeetCode 3173 - Bitwise OR of Adjacent Elements

Difficulty: 🟢 Easy
Topics: Array, Bit Manipulation

Solution

Problem Understanding

The problem gives us an integer array nums of length n. We must create and return a new array called answer of length n - 1.

For every index i, the value at answer[i] should be the result of applying the bitwise OR operation between two adjacent elements in the original array:

$answer[i] = nums[i] \mid nums[i+1]$

The bitwise OR operation compares the binary representation of two numbers. For each bit position:

If either bit is 1, the result bit becomes 1
Only if both bits are 0, the result bit becomes 0

For example:

1 | 3
Binary: 001 | 011 = 011
Result: 3

The input array always contains at least two elements because the constraints guarantee:

2 <= nums.length <= 100

This is important because we always need a pair of adjacent elements to compute an OR value.

The value constraints are also small:

0 <= nums[i] <= 100

This tells us that integer overflow is not a concern, and even a simple linear solution will be more than efficient enough.

The key observation is that every output element depends only on two neighboring elements from the input array. We do not need complicated preprocessing, advanced data structures, or nested computations.

Some important edge cases include arrays with only two elements, arrays containing zeros, and arrays where adjacent elements are identical. The problem guarantees valid input sizes, so we never need to handle empty arrays or arrays of length one.

Approaches

Brute Force Approach

A straightforward brute force solution would examine every adjacent pair one at a time, compute the bitwise OR, and append the result to a new array.

For each index i from 0 to n - 2:

Take nums[i]
Take nums[i + 1]
Compute their OR value
Store the result

This approach is correct because the problem definition directly asks for the OR of every adjacent pair.

Even though this is called a brute force approach, it is already optimal because the problem fundamentally requires examining every adjacent pair at least once.

Optimal Approach

The optimal solution uses a single linear traversal of the array.

The important insight is that each output value depends only on local information, specifically two neighboring elements. There is no dependency between computations, so we can process the array from left to right exactly once.

Since there are n - 1 adjacent pairs, we perform exactly n - 1 OR operations.

This gives us a time complexity of O(n) with minimal additional space besides the output array itself.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Computes OR for each adjacent pair directly
Optimal	O(n)	O(n)	Single pass traversal with immediate result construction

Algorithm Walkthrough

Create an empty result array called answer.

This array will store the OR result for every adjacent pair. 2. Traverse the input array from index 0 to n - 2.

We stop at n - 2 because each computation needs both nums[i] and nums[i + 1]. If we reached the last index, there would be no adjacent element to pair with it. 3. For each index i, compute the bitwise OR of the current element and the next element.

$nums[i] \mid nums[i+1]$ 4. Append the computed value to answer.

Each appended value corresponds directly to one adjacent pair in the original array. 5. After the traversal finishes, return answer.

At this point, the result array contains exactly n - 1 values, which matches the required output size.

Why it works

The algorithm works because every required output value depends only on one adjacent pair in the original array. By iterating through every valid adjacent pair exactly once and computing its OR value, we guarantee that every output position is computed correctly. Since no pair is skipped or repeated, the returned array exactly matches the problem definition.

Python Solution

from typing import List

class Solution:
    def orArray(self, nums: List[int]) -> List[int]:
        answer = []

        for i in range(len(nums) - 1):
            answer.append(nums[i] | nums[i + 1])

        return answer

The implementation begins by creating an empty list called answer, which stores the final results.

The loop iterates from 0 to len(nums) - 2. This ensures that every iteration has access to both the current element and the next element.

Inside the loop, the bitwise OR operation is performed using the | operator:

nums[i] | nums[i + 1]

The computed value is appended directly to the result list.

After processing all adjacent pairs, the method returns the completed list.

The implementation follows the algorithm exactly and uses only a single traversal of the input array.

Go Solution

func orArray(nums []int) []int {
    answer := make([]int, 0, len(nums)-1)

    for i := 0; i < len(nums)-1; i++ {
        answer = append(answer, nums[i]|nums[i+1])
    }

    return answer
}

The Go implementation follows the same logic as the Python version.

One small optimization is preallocating the capacity of the result slice using:

make([]int, 0, len(nums)-1)

This avoids unnecessary reallocations while appending elements.

Go slices are dynamic, so appending computed OR values is straightforward. Integer overflow is not a concern because the constraints are very small.

Worked Examples

Example 1

Input:

nums = [1, 3, 7, 15]

i	nums[i]	nums[i+1]	OR Result	answer
0	1	3	3	[3]
1	3	7	7	[3, 7]
2	7	15	15	[3, 7, 15]

Final output:

[3, 7, 15]

Example 2

Input:

nums = [8, 4, 2]

Binary representations:

8 = 1000
4 = 0100
2 = 0010

i	nums[i]	nums[i+1]	Binary OR	OR Result	answer
0	8	4	1100	12	[12]
1	4	2	0110	6	[12, 6]

Final output:

[12, 6]

Example 3

Input:

nums = [5, 4, 9, 11]

i	nums[i]	nums[i+1]	OR Result	answer
0	5	4	5	[5]
1	4	9	13	[5, 13]
2	9	11	11	[5, 13, 11]

Final output:

[5, 13, 11]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We process each adjacent pair exactly once
Space	O(n)	The output array stores `n - 1` elements

The algorithm performs one pass through the array, making the running time linear in the size of the input. The extra space usage comes entirely from the required output array, since the problem asks us to return a new list containing all computed OR values.

Test Cases

from typing import List

class Solution:
    def orArray(self, nums: List[int]) -> List[int]:
        answer = []

        for i in range(len(nums) - 1):
            answer.append(nums[i] | nums[i + 1])

        return answer

sol = Solution()

assert sol.orArray([1, 3, 7, 15]) == [3, 7, 15]  # provided example
assert sol.orArray([8, 4, 2]) == [12, 6]  # provided example
assert sol.orArray([5, 4, 9, 11]) == [5, 13, 11]  # provided example

assert sol.orArray([0, 0]) == [0]  # minimum size with zeros
assert sol.orArray([1, 1]) == [1]  # identical adjacent elements
assert sol.orArray([0, 5]) == [5]  # OR with zero
assert sol.orArray([100, 100]) == [100]  # maximum constraint values
assert sol.orArray([2, 4, 8, 16]) == [6, 12, 24]  # powers of two
assert sol.orArray([7, 7, 7]) == [7, 7]  # repeated values
assert sol.orArray([0, 1, 0, 1]) == [1, 1, 1]  # alternating zeros and ones

Test	Why
`[1, 3, 7, 15]`	Validates the first provided example
`[8, 4, 2]`	Validates binary OR behavior
`[5, 4, 9, 11]`	Validates mixed values
`[0, 0]`	Tests minimum array size
`[1, 1]`	Tests identical neighbors
`[0, 5]`	Ensures OR with zero works correctly
`[100, 100]`	Tests upper constraint values
`[2, 4, 8, 16]`	Tests distinct bit positions
`[7, 7, 7]`	Tests repeated values
`[0, 1, 0, 1]`	Tests alternating bit patterns

Edge Cases

One important edge case is the minimum allowed array length, where nums contains exactly two elements. In this situation, there is only one adjacent pair, so the output array contains exactly one value. Off by one errors are common here because incorrect loop bounds can accidentally skip the only valid pair. The implementation correctly iterates from 0 to len(nums) - 2, ensuring the pair is processed.

Another important edge case involves zeros. Since the bitwise OR operation with zero leaves the other value unchanged, expressions like 0 | x should return x. Bugs can occur if someone mistakenly uses arithmetic operations instead of bitwise operations. The implementation uses the proper | operator, so these cases are handled naturally.

A third important edge case is arrays with repeated values. For example, if two adjacent elements are both 7, the result should also be 7. Some incorrect implementations may accidentally modify values or use the wrong operator. Because the algorithm directly computes the OR of each adjacent pair independently, repeated values are processed correctly without any special handling.