Given an array nums of length n, return an array answer of length n - 1 such that answer[i] = nums[i] | nums[i + 1] where | is the bitwise OR operation.
Example 1:
Input: nums = [1,3,7,15]
Output: [3,7,15]
Example 2:
Input: nums = [8,4,2]
Output: [12,6]
Example 3:
Input: nums = [5,4,9,11]
Output: [5,13,11]
Constraints:
2 <= nums.length <= 1000 <= nums[i] <= 100Problem Overview: You receive an integer array nums. For every adjacent pair (nums[i], nums[i+1]), compute the bitwise OR and store it in a result array. The output size is n - 1 where n is the length of the input array.
Approach 1: Direct Iteration with Bitwise OR (O(n) time, O(1) space)
The most direct solution walks through the array once and computes nums[i] | nums[i+1] for every index. Bitwise OR combines the bits of two integers, setting each bit if it exists in either operand. Since each adjacent pair is processed exactly once, the algorithm runs in linear time O(n). Aside from the output array, no additional memory is required, giving O(1) auxiliary space. This approach fits naturally with problems involving array traversal and simple bit manipulation operations.
The key observation: the result for each index depends only on the current element and the next one. No preprocessing, sorting, or extra data structures are needed. A simple loop from 0 to n-2 computes the answer. Languages like Python, Java, C++, Go, and TypeScript all provide a built‑in | operator for this operation, making the implementation extremely compact.
Approach 2: Bit-by-Bit Construction (Conceptual) (O(n * b) time, O(1) space)
Instead of using the built-in OR operator, you could construct the result by checking each bit position. For every adjacent pair, iterate through all bit positions (typically up to 31 or 32 bits for integers) and set the bit in the result if it appears in either number. This leads to O(n * b) time where b is the number of bits in the integer representation. Space usage remains O(1) beyond the output array.
This approach rarely makes sense in production code because modern languages already implement OR efficiently at the hardware level. Still, it helps illustrate what the OR operation actually does internally—merging two binary representations bit by bit.
Recommended for interviews: The direct iteration approach is exactly what interviewers expect. Start by recognizing that each result depends only on two adjacent elements, then apply a single pass with the | operator. The brute bit-by-bit construction shows understanding of how bitwise operations work, but the linear iteration solution demonstrates practical coding skills and clean problem decomposition.
We iterate through the first n - 1 elements of the array. For each element, we calculate the bitwise OR value of it and its next element, and store the result in the answer array.
The time complexity is O(n), where n is the length of the array. Ignoring the space consumption of the answer array, the space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Iteration with Bitwise OR | O(n) | O(1) | Best general solution. Simple linear scan using the built-in OR operator. |
| Bit-by-Bit Construction | O(n * b) | O(1) | Useful for understanding how bitwise OR works internally or when practicing low-level bit manipulation. |
3173. Bitwise OR of Adjacent Elements (Leetcode Easy) • Programming Live with Larry • 489 views views
Watch 1 more video solutions →Practice Bitwise OR of Adjacent Elements with our built-in code editor and test cases.
Practice on FleetCode