FastPrep
Problem · Bit Manipulation

Can You Count the Bit Strings?

Learn this problem
● MediumSnowflake logoSnowflakeINTERNOA
See Snowflake hiring insights

Problem statement

A bit string is a string of bits that have values of either 1 or 0, A super bit string is a bit string made by flipping zero or more of the 0s in the bit string to 1. Given k decimal integers, convert each to a bit string that has a given length n. Generate all possible super bitstrings of each of the k bit strings. Finally, perform a union of the super bit strings of all the bit strings and determine its size. This is the number to return.

Function

superBitstrings(n: int, bitStrings: int[]) → int

Complete the function superBitstrings in the editor.

superBitstrings has the following parameters:

  1. 1. n: the required bit string length
  2. 2. int[] bitStrings: an array of decimal integers

Returns

int: the number of unique bitstrings that can be formed from all k values provided.

Examples

Example 1

n = 5bitStrings = [10, 26]return = 8
When converted to strings equal [01010, 11010]. Notethat the value 10 had to be padded with a zero to make itthe required length. Original bit string = 01010    Decimal 10 Flip 0: 01010 Flip 1: 11010 01110         01011 Flip 2: 11110         11011         01111 Flip 3: 11111 Original bit string = 11010 Decimal 26 Flip 0:11010 Flip 1: 11110         11011 Flip 2: 11111 There are 8super bit strings that can be formed from thefirst bit string, and 4 that can be formed from the secondAll of the super bit strings formed from 11010 appear inthe set from 01010, so after the union, there are still only8 super bit strings formed.

Constraints

🍑🍑

More Snowflake problems

drafts saved locally
public int superBitstrings(int n, int[] bitStrings) {
  // write your code here
}
n5
bitStrings[10, 26]
expected8
checking account