Round 1
Questions:
You are given a string s
of length n
denoting a valid binary expression. The string can have the following characters:
x
: Denotes the primary variableX
: Denotes the negation of the primary variable1
: Denotes the logicaltrue
value0
: Denotes the logicalfalse
value&
: Denotes the logicaland
operation|
: Denotes the logicalor
operation^
: Denotes the logicalxor
operation(
: Denotes the start of a subexpression)
: Denotes the end of a subexpression
You need to determine the minimum number of substitutions required (replace any x
or X
with 0
or 1
) to make the expression evaluate to either true
or false
. There are multiple test cases, and you need to print the result for each test case in a new line.
Constraints:
- 1 <=
t
<= 10 - 1 <=
n
<= 10^5 - The expression is always valid.
Sample Input:
5 1&0 x 1|(x^x&(x|0)) 1|0 (0|x|(X^1^x^X))
Sample Output & Explanation:
0 -> The expression is already true 1 -> The expression can be made true or false by replacing x with 1 or 0 0 -> The expression is already true, irrespective of the value of x 0 -> The expression is already false 1 -> We can set x = 1 to make the expression true
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.