Discover final factor in Array shaped from bitwise AND of array parts


View Dialogue

Enhance Article

Save Article

Like Article

View Dialogue

Enhance Article

Save Article

Like Article

Given an array A[] of measurement N, the duty is to search out the final remaining factor in a brand new array B containing all pairwise bitwise ANDs of parts from A i.e., B consists of N⋅(N − 1) / 2 parts, every of the shape Ai & Aj for some 1 ≤ i < j ≤ N. And we will carry out the next operation any variety of instances on a brand new array until there is just one factor remaining akin to:

  • Let X and Y be the present most and minimal parts of array B respectively and take away X and Y from array B and insert X|Y into it.

Examples:

Enter: A[] = {2, 7, 1}
Output: 3
Clarification: Array B will probably be [A1 & A2, A1 & A3, A2 & A3] = [2 & 7, 2 & 1, 7 & 1] = [2, 0, 1].
Then, we do the next operations on B:
Take away 2 and 0 from B and insert 2|0=2 into it. Now, B=[1, 2].
Take away 2 and 1 from B and insert 2|1=3 into it. Now, B=[3].
The final remaining factor is thus 3.

Enter: A[] = {4, 6, 7, 2}
Output: 6

Method: The issue could be solved based mostly on the next remark:

Observations:

  • The property of bitwise or is that if we’re performing X | Y, bit i will probably be set if atleast considered one of bit i in X or Y is about.
  • This leads us to probably the most essential remark of the issue, for each bit i, if bit i is about in atleast considered one of B1, B2, …BN⋅(N−1)/2, then bit i will probably be set within the ultimate remaining factor of B when all of the operations are carried out. We don’t want to fret about how the operations are carried out.
  • For bit i to be set in atleast one factor of B, we have to have atleast 2 parts in A say j and okay the place Aj and Aokay each have bit i set. This units the bit i in Aj & Aokay.
  • Now we’ve got the next resolution, iterate over each legitimate bit i, rely the variety of parts in array A which have bit i set. If this rely is bigger than 1, the ultimate reply may have bit i set else will probably be unset.

Comply with the steps talked about under to implement the concept:

  • Create an array of measurement 32 to retailer the rely of bits set in ith place.
  • Traverse the array and for every array factor:
    • Discover the positions wherein the bit is about.
    • Increment the set bit rely for that place by 1.
  • Traverse the array storing the set bit rely.
    • If the rely is at the very least 2, set that bit within the ultimate reply.
  • Return the quantity shaped because the required reply.

Beneath is the implementation of the above strategy:

Java

  

import java.io.*;

import java.util.*;

  

public class GFG {

  

    

    

    public static int discover(int a[], int n)

    {

        int rely = 0;

        int b[] = new int[33];

        for (int bit = 30; bit >= 0; bit--) {

            for (int i = 0; i < n; i++) {

                if (((1 << bit) & (a[i])) != 0) {

                    b[bit]++;

                }

            }

        }

        for (int bit = 30; bit >= 0; bit--) {

            if (b[bit] > 1)

                rely = rely + (1 << bit);

        }

        return rely;

    }

  

    

    public static void fundamental(String[] args)

    {

        int A[] = { 2, 7, 1 };

        int N = A.size;

  

        

        System.out.println(discover(A, N));

    }

}

Time Complexity: O(N) 
Auxiliary House: O(1)

Leave a Reply