You are given an array with -bit integers: .

BIT(x, i) = (x >> i) & 1, where is the lower bit of in binary form. If we regard every bit as a vertex of a graph G, there is an undirected edge between vertices and if there is a value such that BIT(d[k], i) == 1 && BIT(d[k], j) == 1.

For every subset of the input array, how many connected-components are there in that graph?

A connected component in a graph is a set of nodes which are accessible to each other via a path of edges. There may be multiple connected components in a graph.

Example

In the real challenge, there will be nodes associated with each integer in represented as a bit binary value. For clarity, only bits will be shown in the example but all will be considered in the calculations.

    Decimal  Binary Edges   Node ends
    d[0] = 1   0001   0
    d[1] = 2   0010   0
    d[2] = 3   0011   1       0 and 1
    d[3] = 5   0101   1       0 and 2

Consider all subsets:

                 Edges
    Subset   Count  Nodes  Connected components
    {1}         0           64
    {2}         0           64
    {3}         1   0-1     63
    {5}         1   0-2     63
    {1,2}       0           64
    {1,3}       1   0-1     63
    {1,5}       1   0-2     63
    {2,3}       1   0-1     63
    {2,5}       1   0-2     63
    {3,5}       2   0-1-2   62
    {1,2,3}     1   0-1     63
    {1,2,5}     1   0-2     63
    {1,3,5}     2   0-1-2   62
    {2,3,5}     2   0-1-2   62
    {1,2,3,5}   2   0-1-2   62
    Sum                    944

The values and have bits set, so they have edge each. If a subset contains only a or , there will be one connected component with nodes, and components with node for a total of .

If both and are in a subset, component with nodes and is formed since node is one end of each edge described. The other nodes are solitary, so there are connected components total.

All other values have only bit set, so they have no edges. They have components with node each.

Function Description

Complete the findConnectedComponents function in the editor below.

findConnectedComponents has the following parameters:

  • int d[n]: an array of integers

Returns

  • int: the sum of the number of connected components for all subsets of

Input Format

The first row contains the integer , the size of .
The next row has space-separated integers, .

Constraints


Line: 1 Col: 1
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score