Skip to main content

TCS

TCS OA-22 2024

Problem Description

You are given an integer array arr. Your task is to find the number of distinct bitwise OR results from all possible non-empty subarrays of arr.

A subarray is a contiguous, non-empty sequence of elements within an array. The bitwise OR of a subarray is obtained by performing the bitwise OR operation across all elements within that subarray.

Input Format

  • The first line contains an integer N, representing the array's length.
  • The second line contains N space-separated integers.

Output Format

An integer representing the count of distinct bitwise OR values from all non-empty subarrays of arr.

Constraints

  • 1 ≤ arr.size() ≤ 10⁴
  • 0 ≤ arr[i] ≤ 10³

Example

Sample Input:

3
[1, 2, 4]

Sample Output:

6

Explanation:

  • The distinct bitwise OR values from all subarrays are:Subarray [1]: OR = 1Subarray [2]: OR = 2Subarray [4]: OR = 4Subarray [1, 2]: OR = 3 (1 | 2)Subarray [2, 4]: OR = 6 (2 | 4)Subarray [1, 2, 4]: OR = 7 (1 | 2 | 4)

The distinct OR results are {1, 2, 3, 4, 6, 7}, so the output is 6.