Braille's Dilemma

Hard
0/120
Average time to solve is 24m
profile
Contributed by
15 upvotes
Asked in companies
SprinklrVFISLK Global ServicesCodezero2pi

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
3
11100
11101
01100
2
111
000
Sample Output 1:
5
2
Explanation for Sample Input 1:
For the first test case :
There are three strings.
First Abhishkek will touch the last character of all strings.
For the first and third-string Abhishek will identify 0 for the first and third strings and for the second string Abhishek will identify 1. In this way, Abhishek will be able to distinguish the 2nd string.
Next Abhishek will touch 1st character of the 1st and 3rd string. Abhishek will identify 1 for 1st string and 0 for the third string. In this way, Abhishek will distinguish 1st and 3rd strings.
Thus the total number of touches Abhishek make is 5.

For the second test case :
There are two strings.
Abhishek will touch the first character of the first and second string. Abhishek will identify 1 for 1st string and 0 for the second string. In this way, Abhishek will distinguish 1st and 2nd strings.
Sample Input 2:
2
4
10010
11010
01010
01100
3
000101
100010
111000
Sample Output 2:
 8
 5
Hint

Try bruteforce using bitmasks

Approaches (2)
Brute Force

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'.
Time Complexity

O( (2^k)* n *k ) where n is the number of strings and k is the length of the string.

There will be a total of 2^k recursion calls and in each recursion call, we are running a loop of ‘k’ steps for all ‘n’ strings. Thus the time complexity will be ((2^k)*n*k).

Space Complexity

O((2^n) ) where n is the number of strings.

The recursion stack will have space complexity O(2^n). hence the space complexity will be (2^n).

Code Solution
(100% EXP penalty)
Braille's Dilemma
Full screen
Console