Find the minimum number of inversions needed to make an expression balanced
Given an expression consisting of an opening brace { and a closing brace }, find the minimum number of inversions needed to balance the expression.
For example,
Input: {{}{{}{{
Output: Minimum number of inversions needed is 2
{{}{{}{{ ——> {{}{{}}{ ——> {{}{{}}}
Input: {{{{{{
Output: Minimum number of inversions needed is 3
{{{{{{ ——> {{{}{{ ——> {{{}}{ ——> {{{}}}
Output: Minimum number of inversions needed is 2
{{}{{}{{ ——> {{}{{}}{ ——> {{}{{}}}
Input: {{{{{{
Output: Minimum number of inversions needed is 3
{{{{{{ ——> {{{}{{ ——> {{{}}{ ——> {{{}}}
The idea is to traverse the given expression and maintain a count of open braces in the expression seen.
- If the current character is an opening brace
{, increment the opened braces count by1. - If the current character is a closing brace
}, check if it has an unclosed brace to its left (look for non-zero opened brace count). - If any unclosed brace is found, close it using the current brace and decrement the count of opened braces by
1. - Otherwise, convert the current closing brace
}to{and increment the total inversions needed and the opening brace count by1. - After we are done processing each character in the expression, if there are
nopened braces, we will need exactlyn/2inversion to close them.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include <iostream> #include <string> using namespace std; // Function to find the minimum number of inversions needed // to make the given expression balanced int findMinInversions(string exp) { // if the expression has an odd length, it cannot be balanced if (exp.length() & 1) { return -1; } int inversions = 0; // stores total inversions needed int open = 0; // stores the total number of opening braces // traverse the expression for (int i = 0; i < exp.length(); i++) { // if the current character is an opening brace if (exp[i] == '{') { open++; } // if the current character is a closing brace else { // if an opening brace is found before, close it if (open) { open = open - 1; // decrement opening brace count } // invert the closing brace, i.e., change '}' to '{' else { inversions++; // increment total inversions needed by 1 open = 1; // increment opening brace count } } } // for `n` opened braces, exactly `n/2` inversions are needed return inversions + open/2; } int main() { string exp = "{{}{{}{{"; int inv = findMinInversions(exp); if (inv != -1) { cout << "The minimum number of inversions needed is " << inv; } else { cout << "Invalid input" << endl; } return 0; } |
Output:
The minimum number of inversions needed is 2
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
class Main { // Function to find the minimum number of inversions needed // to make the given expression balanced public static int findMinInversions(String exp) { // if the expression has an odd length, it cannot be balanced if (exp == null || exp.length() % 2 == 1) { return -1; } int inversions = 0; // stores total inversions needed int open = 0; // stores the total number of opening braces // traverse the expression for (char c: exp.toCharArray()) { // if the current character is an opening brace if (c == '{') { open++; } // if the current character is a closing brace else { // if an opening brace is found before, close it if (open != 0) { open = open - 1; // decrement opening brace count } // invert the closing brace, i.e., change '}' to '{' else { inversions++; // increment total inversions needed by 1 open = 1; // increment opening brace count } } } // for `n` opened braces, exactly `n/2` inversions are needed return inversions + open / 2; } public static void main(String[] args) { String exp = "{{}{{}{{"; int inversions = findMinInversions(exp); if (inversions != -1) { System.out.print("The minimum number of inversions needed is " + inversions); } else { System.out.print("Invalid input"); } } } |
Output:
The minimum number of inversions needed is 2
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
# Function to find the minimum number of inversions needed # to make the given expression balanced def findMinInversions(exp): # if the expression has an odd length, it cannot be balanced if len(exp) % 2: return -1 inversions = 0 # stores total inversions needed open = 0 # stores the total number of opening braces # traverse the expression for i in range(len(exp)): # if the current character is an opening brace if exp[i] == '{': open = open + 1 # if the current character is a closing brace else: # if an opening brace is found before, close it if open: open = open - 1 # decrement opening brace count else: # invert the closing brace, i.e., change '}' to '{' inversions = inversions + 1 # increment total inversions needed by 1 open = 1 # increment opening brace count # for `n` opened braces, exactly `n/2` inversions are needed return inversions + open // 2 if __name__ == '__main__': exp = '{{}{{}{{' inv = findMinInversions(exp) if inv != -1: print('The minimum number of inversions needed is', inv) else: print('Invalid input') |
Output:
The minimum number of inversions needed is 2
The time complexity of the above solution is O(n), where n is the length of the input expression, and doesn’t require any extra space.
Also See:
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)