Braille's Dilemma

Posted: 6 Dec, 2020
Difficulty: Hard


Try Problem

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 changes Abhishek has to make to distinguish between all given ‘N’ strings.
You do not need to print anything, it has already been taken care of. Just implement the given function.
1 <= T <= 10
3 <= N <= 10
1 <= n <= 100
Where n  is the length of string. 
All the strings are distinct.

Time Limit: 1 sec
Approach 1

The key idea is to check for all characters of all the strings. We will create a variable mask that will tell how many strings we need to work on. If the i-th bit of mask is 1 then it means we need to work on the i-th string. Initially, the value of the mask will be 2^N -1(In this the first N bits from the right are 1). We will first check the first character of all strings. The strings having 1st character as 1 will come together and strings having 0 characters will come together. Now similarly we will distinguish between strings having 1st character as 1 and strings having first character 0. For this, we will use recursion. If not checking the first character we can move to the next character.


Algorithm :

  • Create variable mask = (2^N) - 1.
  • Create a recursive function count_steps(int mask, String arr[],int n,int N, int pos = 0) where n is the size of string.
  • Add the condition that if the number of bits in mask is 1 then it means all the strings have been recognized so return 0.
  • Add the base case for count_steps function such that if pos == n then return infinite
  • Create two-variable mask1 =0 and mask2 =0 to group strings having pos character 1 and 0.
  • Run a loop from 0 to N. if the i-th bit is 1 in the mask then it means we need to work on i-th string. Now check the pos character of i-th string. If it is 1 then set the ith bit mask2 else set the ith bit mask1. In this way, we are grouping the strings having 0 and 1’s bits.
  • The recursive call will be:-

Here cnt is the number of set bits in the mask.

  • In the end return min(a,b).
Try Problem