algoadvance

Leetcode 2980. Check if Bitwise OR Has Trailing Zeros

Problem Statement

You are given an array of integers arr and an integer k. Your task is to determine whether any subarray of arr with length k has a bitwise OR result with at least one trailing zero. In other words, you need to find whether there exists a subarray of length k such that the result of the bitwise OR operation on all elements of the subarray ends with a zero bit.

Return true if any such subarray exists. Otherwise, return false.

Clarifying Questions

1. What are the constraints on the size of the array arr and the value of k?
   • Typically, constraints such as 1 <= arr.length <= 10^5 and 1 <= k <= arr.length could be assumed.
2. Can the array contain negative integers?
   • Assuming standard constraints, the array might only contain non-negative integers.
3. Are there any restrictions on the values within the array?
   • Assuming typical integer range constraints, e.g., 0 <= arr[i] <= 10^9.

Strategy

1. Iterate through all possible subarrays of length k.
2. Calculate the bitwise OR of each subarray.
3. Check if there’s a trailing zero in the result of the bitwise OR operation. A number has a trailing zero if (number & 1) == 0.

Using a sliding window approach will help to optimize the process and maintain a constant time window checking.

Time Complexity

The solution will iterate through elements once, giving a time complexity of O(n), where n is the length of the array.

Code

Here is the implementation of the strategy described:

public class Solution {
    public boolean hasTrailingZeroSubarray(int[] arr, int k) {
        // Initial bitwise OR for the first window
        int windowOr = 0;
        
        // Calculate the bitwise OR for the first `k` elements
        for (int i = 0; i < k; i++) {
            windowOr |= arr[i];
        }
        
        // Check if the first window has trailing zero
        if ((windowOr & 1) == 0) {
            return true;
        }
        
        // Sliding window approach
        for (int i = k; i < arr.length; i++) {
            // Remove the influence of the previous element
            windowOr &= ~(arr[i - k]);
            // Add the new element to the window OR
            windowOr |= arr[i];
            
            // Check if this new window has a trailing zero
            if ((windowOr & 1) == 0) {
                return true;
            }
        }
        
        // If no window meets the condition, return false
        return false;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.hasTrailingZeroSubarray(new int[]{1, 2, 4, 8, 16}, 3)); // Example test case
    }
}

Explanation

• We initialize windowOr to calculate the bitwise OR of the first k elements.
• A sliding window approach is then used to check the rest of the elements in the array:
  • We remove the contribution of the element that is sliding out of the window using bitwise operations.
  • We then add the new element that is entering the window.
  • After updating windowOr, we check if it satisfies the trailing zero condition.
• If any subarray meets the condition of having a trailing zero in its OR result, we return true.
• If after checking all possible subarrays no such subarray is found, we return false.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?