HiLabs SDE: Online Assessment Problem

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 variable
• X: Denotes the negation of the primary variable
• 1: Denotes the logical true value
• 0: Denotes the logical false value
• &: Denotes the logical and operation
• |: Denotes the logical or operation
• ^: Denotes the logical xor 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