Union of super bit strings

help
, ,
1

There is an array of numbers of size n.
A bit string of a number is binary representation of that number. given an integer k we can get n
k-bit strings .
ex: n=2, k=5 array={10,26}, then bit strings are 01010, 11010.
(we should add padding of 0’s on left if necessary and It is guaranteed that max number in array < 2^k).
super bit string of a bit string is formed by alternating 0 or more no: of 0’s in the bit string
ex: super bit strings of 11010 are {11010, 11110, 11011, 11111}

Our objective is to find size of union of super bit strings of the n k-bit strings.

input: k<=18, n<=50000, a[i]<=262144

ex: n=2, k=5 array={10,26}, then size of union of super bit strings is 8.
10 - 01010, 26 - 11010.

1 Like
2

Let A=and of all elements,ans=2^(k-number of set bits (A))

3

counter example:
let 2 bit strings of the array are {111000, 000111}
no: of super bit strings = 8,8
and ={000000}
no: of super bit strings = 2^6 = 64

4

Sry i was in hurry,so i want to tell you it can be solved using bfs or dfs ,make all the combinations of one number you select and visit all the states making its boolean true,and then select 2nd number apply same dfs,only dfs if it is not visited already ,do this for all numbers in array,its complexity will be atmost 2*2^18.count number of visited states,that will be your answer.hope this helps.

2 Likes