Maximizing Groups with Minimum Bitwise OR Sum

You are given a sequence of n non‐negative integers. You can partition these numbers into arbitrarily many groups (the groups need not be formed by contiguous segments). For each group, compute the bitwise OR of its elements, and then take the sum of these OR values. Your task is to partition the numbers in such a way that the overall sum is minimized, and among all such partitions, find the maximum possible number of groups.

Problem Analysis:

If you combine all the numbers into one group, the bitwise OR equals \(S = a_1 \lor a_2 \lor \cdots \lor a_n\). In any valid partition, note that each bit that is set in \(S\) must appear at least once, so the minimum possible sum is \(S\). However, if the same bit appears in more than one group, it will be counted multiple times. Hence, to achieve the minimum sum of \(S\), each bit in \(S\) must appear in exactly one group.

This creates a constraint: for each bit set in \(S\), all numbers that contribute that bit must be placed in the same group. In other words, if an element has two or more bits set, it forces their respective bits to be in the same group. Thus, you can view the bits as vertices in a graph. For every number, if it has bits \(b_1, b_2, \ldots, b_k\) set, then for every pair \((b_i, b_j)\) add an edge. The maximum number of groups (while keeping the sum minimal) is equal to the number of connected components in this graph.

Special Case: If \(S = 0\) (i.e. all numbers are 0), then the bitwise OR of any group is 0. In this case, you can partition the numbers into \(n\) groups, so the answer will be \(n\).

Input and Output:

The input consists of an integer \(n\) followed by \(n\) non‐negative integers. Output the maximum number of groups that can be formed so that the sum of the bitwise OR values of the groups is minimized.

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 10^5\)), denoting the number of elements.
The second line contains \(n\) space-separated non-negative integers \(a_1, a_2, \ldots, a_n\) (each \(a_i\) fits in a 32-bit integer).

outputFormat

Output a single integer, which is the maximum number of groups that can be formed such that the total sum of bitwise OR values over all groups is minimized.

sample

2
1 2

2