- 1of 1 vote
Each test file starts with an integer ‘t’ - the number of testcases.
In each of the next ‘t’ lines, you are given a string of ‘n’ characters [ either ‘(‘ or ’)’ or ‘*’ ].
Your task is to find the number of distinct balanced parentheses expressions you can make by replacing the ‘*’ with either ‘(‘ or ‘)’ or removing the ‘*’
Note : You have to replace each ‘*’ with one of ‘(‘ or ‘)’ or remove it. If removed, assume the string has reduced by 1 character.
Duplicate strings are not allowed. The final expressions to be counted have to be distinct
As the answer may be large, please output it modulo 1000000007 (10^9+7)
Output one integer per line corresponding to each testcase.
1 <= t <= 20
1 <= n <= 100
0 <= Number of ‘*’ in the input string <= min(n,10)
The five possible valid solutions are for the first input are :
The nine possible valid solutions are for the second input are :
- 0of 0 votes
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is ??
a) theta(n) b) theta(log n) c) theta(log*n) d) theta(1)
- -1of 1 vote
how many elements can be sorted in theta(log n) time using heap sort ?