Last Updated: 6 Dec, 2020

Braille's Dilemma

Hard

Asked in companies

Solve now

Problem statement

Abhishek, a blind man has N distinct binary strings all of the equal lengths. A binary string only contains '0's and '1's. The strings are numbered from 1 to N and all are distinct strings. Abhishek can only differentiate between these strings by touching them. In one touch Abhishek can identify one character at a position of any particular string from the set. Your task is to find the minimum number of touches Abhishek has to make so that he finds that all strings are different.

Input Format:

The first line of input contains an integer T, the number of test cases.

 The first line of each test case contains a single integer ‘N’ denoting the number of strings given.

 From the second line onwards the next line ‘N’ lines of the test case contains distinct strings.

Output Format:

Return an integer denoting the minimum number of touches Abhishek has to make to distinguish between all given ‘N’ strings.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
3 <= N <= 10
1 <= k <= 100
Where k  is the length of the string. 
All the strings are distinct.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Algorithm:-

Initialize a variable 'k' with 'arr[0].size' to store the length of the binary string.
Return the recursive function with the value of the current mask as 2^'n' - 1;
Create a recursive function 'count_steps(int mask, String arr[], int k, int n)' where n is the size of the string.
When 'mask' contains only 1 bit it means every string is recognized.
- Return 0;
Initialize a variable 'ans' = 1e9 to store the answer for current mask.
Checking for each position from '0' to 'k-1' where 'k' is the size of binary strings, to find the minimum answer.
- Create two variables 'mask1' = 0 and 'mask2' = 0 to group strings having pos character 1 and 0.
- Declare a variable 'cnt' to store the total number of touches for the current 'pos'.
- Iterate over all the strings for variable 'i' from 0 to 'n-1' to split the strings based on character at ‘pos’th position.
  - If position 'i' is set in mask means we have to check for the ith string.
    - Increment cnt.
    - check if 'arr[i][pos]' == 1.
      - Set the ith bit in mask2's binary representation.
    - Else
      - Set the ith bit in mask1's binary representation.
- Check if 'mask1' is greater than 0 and 'mask2' is greater than zero.
  - Declare a variable 'a' to store the answer of the recursive function for 'mask1'.
  - Declare a variable 'b' to store the answer of the recursive function for 'mask2'.
  - Make 'ans' = min('ans', 'cnt'+'a'+'b').
Return 'ans'.

Solve now

02 Approach

Approach:-

There are overlapping subcases in Approach1. Hence to optimize it we will use memoization. The memoization state will be dp[mask]. It will tell us the minimum number of touches to make when the state of strings we need to work on is given by mask for all the possible positions. This is similar to memoization with bitmasking. In the count_steps function, we need to add a memoization condition such that if dp[mask]!= -1 then return dp[mask]. In the end dp[mask] = minimum among all the answers for each position.

Algorithm:-

Initialize a variable 'k' with 'arr[0].size' to store the length of the binary string.
Initialize a 'dp' of size ‘2^n’ with -1.
Return the recursive function with the value of the current mask as 2^'k' - 1.
Create a recursive function count_steps(int 'mask', String arr[], int 'k', int 'n', vector<int>&'dp') where 'k' is the size of string.
When 'mask' contains only 1 bit, it means every string is recognized.
- Return 0;
Initialize a variable 'ans' = 1e9 to store the answer for current mask.
Adding memoization condition.
Checking for each position from '0' to 'k-1' where 'k' is the size of binary strings, to find the minimum answer.
- Create two-variable 'mask1' = 0 and 'mask2' = 0 to group strings having pos character 1 and 0.
- Declare a variable 'cnt' to store the total number of touches for the current 'pos'.
- Iterate over all the strings for variable 'i' from 0 to 'N-1' to split the strings based on character at ‘pos’-th position.
  - If position 'i' is set in mask means we have to check for the ith string.
    - Increment cnt.
    - check if 'arr[i][pos]' == 1.
      - Set the ith bit in 'mask2's binary representation.
    - Else
      - Set the ith bit in 'mask1's binary representation.
- Check if 'mask1' is greater than 0 and 'mask2' is greater than zero.
  - Declare a variable 'a' to store the answer of the recursive function for 'mask1'.
  - Declare a variable 'b' to store the answer of the recursive function for 'mask2'.
  - Make 'ans' = min('ans', 'cnt'+'a'+'b').
Return 'dp[mask]' = 'ans'.

Solve now