Given a number N, the task is to insert the minimum number of opening and closing parenthesis into the number N such that the resultant string is balanced and every digit D is exactly in D pairs of matching parenthesis.
Examples:
Input: N = 312
Output: (((3))1(2))
Explanation:
Every digit in the number is within exactly in D parenthesis.
There are other possible strings like (((3)))(1)((2)) but the string obtained is the string that can be formed with the minimum number of parenthesis.Input: N = 111000
Output: (111)000
Explanation:
Every digit in the number is within exactly D parenthesis.
There are other possible strings like (1)(1)(1)000, (11)(1)000 but the string obtained is the string that can be formed with the minimum number of parenthesis.
Approach: The idea is to use an array to keep the track of the number of parentheses that needs to be added.
For any number, the minimum number of parentheses can be added only by nesting the numbers within the parentheses.
For example: let N = 321.
- Initially, an empty array A[] is created.
- The given number is iterated digit wise.
- Initially, D number of opening parentheses are added in the array in order to store the number. Therefore, for the digit 3, 3 opening brackets are added in the array.
- In the next iteration, the digit can be either greater than or less than the previous digit. If the next digit is smaller like 2 in the above example, 3 – 2 = 1 brackets are closed.
- Similarly, if the next digit is greater, the absolute difference number of brackets are opened.
- Repeat the above two steps for all the digits in the given number N. Finally, the string obtained is formed with a minimum number of parentheses.
Below is the implementation of the above approach:
# Python program to find the balanced # parentheses using the given number # Function to find the balanced # parentheses using the given number def balance(m): # Making the list of the # given number m = [int(i) for i in m] # Empty list to store the # parentheses n = [] # Iterating through the # digits of the number for i in m: # Calculating the difference between # opening and closing braces for the # digit if (n.count('(')-n.count(')'))<= i: # If the next digit is greater, # then open the brackets while (n.count('(')-n.count(')')) != i: n.append('(') n.append(i) # Similarly, find the difference # between opening and closing braces elif (n.count('(')-n.count(')'))>i: # If the next digit is smaller, # then close the brackets while (n.count('(')-n.count(')'))!= i: n.append(')') n.append(i) # Finally, close the remaining brackets while (n.count('(')-n.count(')'))!= 0: n.append(')') # Returning the string return ''.join(map(str, n)) # Driver code if __name__ == "__main__": N = 312 print(balance(str(N))) |
(((3))1(2))
Time Complexity: O(K2), where K is the sum of the digits of the number N.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
