Skip to main content
Talentd

Bitwise OR of Adjacent Elements - Solution & Explanation

EasyPremiumFree on FleetCodeArrayBit Manipulation5 min readAsked at: Adobe
Practice this problem

Problem Statement

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 <= 100
  • 0 <= nums[i] <= 100

Approach Overview

Problem 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.

Solution

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Iteration with Bitwise ORO(n)O(1)Best general solution. Simple linear scan using the built-in OR operator.
Bit-by-Bit ConstructionO(n * b)O(1)Useful for understanding how bitwise OR works internally or when practicing low-level bit manipulation.

Video Solution

3173. Bitwise OR of Adjacent Elements (Leetcode Easy) • Programming Live with Larry • 500 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Bitwise OR of Adjacent Elements easy or hard?
Bitwise OR of Adjacent Elements is categorized as an Easy problem. It mainly checks whether you understand array traversal and the behavior of the bitwise OR operator, making it suitable for beginner-level practice.
Bitwise OR of Adjacent Elements Python/Java solution
The solution in Python or Java uses a simple loop and the | operator. For each index i, compute nums[i] | nums[i+1] and store the value in the result array. The logic is identical across Python, Java, C++, Go, and TypeScript.
How to solve Bitwise OR of Adjacent Elements in O(n)?
Loop through the array from index 0 to n-2. For each position, compute nums[i] | nums[i+1] and append the value to the result array. This single linear pass ensures O(n) time complexity and constant auxiliary space.
What is the best approach for Bitwise OR of Adjacent Elements?
Direct iteration with the bitwise OR operator is the best approach. Traverse the array once and compute nums[i] | nums[i+1] for every index. This produces the result array in O(n) time with O(1) extra space.
Is Bitwise OR of Adjacent Elements asked at Google/Amazon/Meta?
Problems involving bit manipulation and array traversal frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact question may vary, similar tasks testing bitwise operations and linear scans are common in early interview rounds.
What data structure is used in Bitwise OR of Adjacent Elements?
The problem primarily uses a simple array. The algorithm iterates through the input array and builds another array containing the OR result of each adjacent pair. No additional complex data structures are required.
What is the time complexity of Bitwise OR of Adjacent Elements?
The optimal solution runs in O(n) time because each adjacent pair in the array is processed exactly once. Only a single pass through the array is required, and each bitwise OR operation runs in constant time.

Ready to solve this problem?

Practice Bitwise OR of Adjacent Elements with our built-in code editor and test cases.

Practice on FleetCode
Previous

Neighboring Bitwise XOR