Check if Bitwise OR Has Trailing Zeros solution and explanation
9 more videos on this problem
Leetcode | 2980. Check if Bitwise OR Has Trailing Zeros | Easy | Java SolutionDeveloper Docs · 3:01 · 511 views
100166. Check if Bitwise OR Has Trailing Zeros || leetcode biweekly contest solutionsilent coder · 0:25 · 285 views
Check if Bitwise OR Has Trailing Zeros - Leetcode 2980 - PythonCheatCode Ninja · 2:28 · 216 views
leetcode weekly contest 378 problem no 1:Check if Bitwise OR Has Trailing ZerosEatCodeAndSleep · 0:11 · 188 views
2980. Check if Bitwise OR Has Trailing Zeros (Leetcode Easy)Programming Live with Larry · 2:15 · 146 views
2980. Check if Bitwise OR Has Trailing Zeros | Weekly Contest 378 | Leetcode | Easy ExplanationRapid Syntax · 10:04 · 143 views
2980. Check if Bitwise OR Has Trailing Zeros || Leetcode Weekly Contest 378Ashish Kumar · 10:41 · 142 views
2980. Check if Bitwise OR Has Trailing Zeros | Weekly 378Tech Courses · 4:13 · 126 views
LeetCode: 2980. Check if Bitwise OR Has Trailing Zeros | Day 28CodeWithMaaz · 8:19 · 84 views
Check if Bitwise OR Has Trailing Zeros | Leetcode 2980 | Approach + Code with explanation.Pirai's Academy · 6:43 · 77 views
The problem
You are given an array of positive integers nums.
You have to check if it is possible to select two or more elements in the array such that the bitwise OR of the selected elements has at least one trailing zero in its binary representation.
For example, the binary representation of 5, which is "101", does not have any trailing zeros, whereas the binary representation of 4, which is "100", has two trailing zeros.
Return true if it is possible to select two or more elements whose bitwise OR has trailing zeros, return false otherwise.
Example 1:
Input: nums = [1,2,3,4,5] Output: true Explanation: If we select the elements 2 and 4, their bitwise OR is 6, which has the binary representation "110" with one trailing zero.
Example 2:
Input: nums = [2,4,8,16] Output: true Explanation: If we select the elements 2 and 4, their bitwise OR is 6, which has the binary representation "110" with one trailing zero. Other possible ways to select elements to have trailing zeroes in the binary representation of their bitwise OR are: (2, 8), (2, 16), (4, 8), (4, 16), (8, 16), (2, 4, 8), (2, 4, 16), (2, 8, 16), (4, 8, 16), and (2, 4, 8, 16).
Example 3:
Input: nums = [1,3,5,7,9] Output: false Explanation: There is no possible way to select two or more elements to have trailing zeros in the binary representation of their bitwise OR.
Constraints:
2 <= nums.length <= 1001 <= nums[i] <= 100
Approach overview
Problem Overview: You are given an integer array and must determine whether there exists a pair of elements whose bitwise OR ends with a trailing zero in binary. A trailing zero means the least significant bit (LSB) of the result is 0. The key observation is that a bitwise OR only produces a 0 in the last bit if both numbers already have 0 there.
Approach 1: Check Pairs for Trailing Zeros (O(n²) time, O(1) space)
The direct approach checks every pair of numbers in the array. For each pair (nums[i], nums[j]), compute nums[i] | nums[j] and test whether the result has a trailing zero. You can verify this with a bit check like ((nums[i] | nums[j]) & 1) == 0. This works because the least significant bit determines whether a number is even or odd. The algorithm iterates through all n(n−1)/2 pairs, which makes the time complexity O(n²), while only constant extra memory is used. This approach clearly demonstrates the property of the OR operation but becomes inefficient for large arrays.
Approach 2: Check Individual Elements for Trailing Zeros (O(n) time, O(1) space)
A more efficient solution comes from analyzing the bit behavior. For a | b to end with 0, both a and b must have their least significant bit equal to 0. In other words, both numbers must be even. Instead of evaluating pairs, scan the array once and count how many numbers are even. As soon as you find at least two even numbers, you know their OR will also be even and therefore contain a trailing zero. The scan requires a single pass with a simple bit check like (num & 1) == 0. This reduces the runtime to O(n) with O(1) space.
This optimization relies on understanding how bitwise operations behave at the bit level. The least significant bit controls parity, and the OR operator only outputs 0 when both inputs have 0. Recognizing this removes the need for pairwise comparisons entirely. Problems like this frequently appear in bit manipulation practice because they reward pattern recognition rather than brute force enumeration.
Recommended for interviews: Start by explaining the pair-checking method to demonstrate correctness and understanding of the OR operation. Then derive the optimized approach by analyzing the least significant bit and parity of numbers. Interviewers typically expect the O(n) scan because it shows you understand binary properties instead of relying on brute force. This pattern appears often in problems involving arrays and bitwise operations.
Approach 1: Approach 1: Check Pairs for Trailing Zeros
In this approach, we will iterate through all possible pairs of elements in the array and check if their bitwise OR results in a number that has at least one trailing zero in its binary representation. We can check for trailing zeros using the condition (num & 1) == 0 for any integer num.
def has_trailing_zero(num):
return (num & 1) == 0
def check_bitwise_or_with_trailing_zero(nums):
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if has_trailing_zero(nums[i] | nums[j]):
return True
return Falseimport java.util.List;
public class Solution {
public boolean hasTrailingZero(int num) {
return (num & 1) == 0;
}
public boolean checkBitwiseORWithTrailingZero(List<Integer> nums) {
int n = nums.size();
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(hasTrailingZero(nums.get(i) | nums.get(j))) {
return true;
}
}
}
return false;
}
}#include <vector>
#include <iostream>
using namespace std;
bool hasTrailingZero(int num) {
return (num & 1) == 0;
}
bool checkBitwiseORWithTrailingZero(vector<int>& nums) {
int n = nums.size();
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(hasTrailingZero(nums[i] | nums[j])) {
return true;
}
}
}
return false;
}function hasTrailingZero(num) {
return (num & 1) === 0;
}
function checkBitwiseORWithTrailingZero(nums) {
for(let i = 0; i < nums.length; i++) {
for(let j = i + 1; j < nums.length; j++) {
if(hasTrailingZero(nums[i] | nums[j])) {
return true;
}
}
}
return false;
}#include <stdbool.h>
bool hasTrailingZero(int num) {
return (num & 1) == 0;
}
bool checkBitwiseORWithTrailingZero(int* nums, int numsSize) {
for(int i = 0; i < numsSize; i++) {
for(int j = i + 1; j < numsSize; j++) {
if(hasTrailingZero(nums[i] | nums[j])) {
return true;
}
}
}
return false;
}using System;
using System.Collections.Generic;
public class Solution {
public static bool HasTrailingZero(int num) {
return (num & 1) == 0;
}
public static bool CheckBitwiseORWithTrailingZero(List<int> nums) {
int n = nums.Count;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(HasTrailingZero(nums[i] | nums[j])) {
return true;
}
}
}
return false;
}
}The Python implementation defines a helper function has_trailing_zero to check for trailing zeros. It iterates through pair combinations from the input list, checking their bitwise OR results.
The time complexity is O(n^2), while the space complexity remains O(1).
Approach 2: Approach 2: Check Individual Elements for Trailing Zeros
If any single number in the array has a trailing zero, then selecting any two or more numbers that include it would definitely have trailing zeros in their OR result. Hence, just a single check over each number's binary representation is required.
def has_trailing_zero(num):
return (num & 1) == 0
def check_bitwise_or_with_trailing_zero(nums):
for num in nums:
if has_trailing_zero(num):
return True
return Falseimport java.util.List;
public class Solution {
public boolean hasTrailingZero(int num) {
return (num & 1) == 0;
}
public boolean checkBitwiseORWithTrailingZero(List<Integer> nums) {
for(int num : nums) {
if(hasTrailingZero(num)) {
return true;
}
}
return false;
}
}#include <vector>
#include <iostream>
using namespace std;
bool hasTrailingZero(int num) {
return (num & 1) == 0;
}
bool checkBitwiseORWithTrailingZero(vector<int>& nums) {
for(const auto& num : nums) {
if(hasTrailingZero(num)) {
return true;
}
}
return false;
}function hasTrailingZero(num) {
return (num & 1) === 0;
}
function checkBitwiseORWithTrailingZero(nums) {
for(let num of nums) {
if(hasTrailingZero(num)) {
return true;
}
}
return false;
}#include <stdbool.h>
bool hasTrailingZero(int num) {
return (num & 1) == 0;
}
bool checkBitwiseORWithTrailingZero(int* nums, int numsSize) {
for(int i = 0; i < numsSize; i++) {
if(hasTrailingZero(nums[i])) {
return true;
}
}
return false;
}using System;
using System.Collections.Generic;
public class Solution {
public static bool HasTrailingZero(int num) {
return (num & 1) == 0;
}
public static bool CheckBitwiseORWithTrailingZero(List<int> nums) {
foreach(int num in nums) {
if (HasTrailingZero(num)) {
return true;
}
}
return false;
}
}In Python, this solution checks each number in the input list, and if any number has a trailing zero, it immediately returns true.
The time complexity is O(n), while the space complexity is O(1).
Approach 3: Counting Even Numbers
According to the problem statement, if there are two or more elements in the array whose bitwise OR operation results in trailing zeros, then there must be at least two even numbers in the array. Therefore, we can count the number of even numbers in the array. If the count of even numbers is greater than or equal to 2, then return true, otherwise return false.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
function hasTrailingZeros(nums: number[]): boolean {
let cnt = 0;
for (const x of nums) {
cnt += (x & 1) ^ 1;
}
return cnt >= 2;
}func hasTrailingZeros(nums []int) bool {
cnt := 0
for _, x := range nums {
cnt += (x&1 ^ 1)
}
return cnt >= 2
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Check Pairs for Trailing Zeros | The time complexity is |
| Approach 2: Check Individual Elements for Trailing Zeros | The time complexity is |
| Counting Even Numbers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Check All Pairs with Bitwise OR | O(n²) | O(1) | Good for explaining brute force logic or when constraints are very small |
| Count Even Numbers (Bit Check) | O(n) | O(1) | Optimal approach; uses parity insight to avoid pair comparisons |
Frequently asked questions
Is Check if Bitwise OR Has Trailing Zeros easy or hard?
Check if Bitwise OR Has Trailing Zeros is classified as an Easy problem. The key challenge is recognizing the binary property that an OR result has a trailing zero only when both operands are even. Once that observation is made, the solution becomes a simple linear scan.
Check if Bitwise OR Has Trailing Zeros Python/Java solution
In Python or Java, iterate through the array and check if each element is even using a bit operation like num & 1. Maintain a counter for even numbers and return true once it reaches two. The implementation is short and runs in O(n) time with O(1) extra space.
How to solve Check if Bitwise OR Has Trailing Zeros in O(n)?
Iterate through the array and check the least significant bit of each number. If (num & 1) == 0, the number is even. As soon as two even numbers are found, their bitwise OR will also have a trailing zero. This single-pass scan gives an O(n) time solution with constant extra memory.
What is the best approach for Check if Bitwise OR Has Trailing Zeros?
The optimal approach scans the array once and counts how many numbers are even. A bitwise OR produces a trailing zero only when both numbers have their least significant bit equal to 0. If the array contains at least two even numbers, their OR will also be even. This method runs in O(n) time and O(1) space.
Is Check if Bitwise OR Has Trailing Zeros asked at Google/Amazon/Meta?
Problems involving bitwise operations and parity checks frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying concept of analyzing bit patterns and optimizing from O(n^2) to O(n) is a common interview expectation.
What data structure is used in Check if Bitwise OR Has Trailing Zeros?
The problem primarily uses a simple array traversal combined with bit manipulation. No additional data structures such as hash maps or stacks are required. The optimized solution only checks each element’s least significant bit.
What is the time complexity of Check if Bitwise OR Has Trailing Zeros?
The brute force method checks every pair and takes O(n^2) time with constant space. The optimized solution scans the array and counts even numbers using a bit check like (num & 1) == 0. That reduces the complexity to O(n) time and O(1) space.