C++ Solution in O(n) time
\nclass Solution {\npublic:\n    int minAddToMakeValid(string s) {\n        int cc = 0, cur = 0;\n        for(auto i: s){\n            if(i == \'(\') ++cur;\n  
```\nclass Solution {\npublic:\n    int minAddToMakeValid(string s) {\n        int cc = 0, cur = 0;\n        for(auto i: s){\n            if(i == \'(\') ++cur;\n            else --cur;\n            if(cur < 0) ++cc, ++cur;\n        }\n        cc += cur;\n        return cc;\n    }\n};\n```
[]