Watch 2 video solutions for Bitwise OR of Adjacent Elements, a easy level problem involving Array, Bit Manipulation. This walkthrough by Programming Live with Larry has 489 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |