Last active
May 10, 2019 18:11
-
-
Save adryanf/5776fc9f1b29c42e7bf7591bd18f0fdd to your computer and use it in GitHub Desktop.
Number of valid parentheses combinations
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//inefficient O(n^2) | |
// Improvement Ideas | |
// The binary numbers must be balanced - equal number of 0s and 1s - maybe there's an efficient way to find out these numbers | |
// | |
function getNumberOfValidParenthesesCombinationsOfN(n){ | |
var i; | |
var maxValue = Math.pow(2, 2*n); | |
var totalNumberOfCombinations = 0; | |
for(i=0; i<maxValue; i++) { | |
// console.log(i); | |
var x = i; | |
var bitStack = []; | |
var debugParColletor = ""; | |
var debugBitColletor = ""; | |
// In reverse order so first LSB, last MSB | |
// 0 -> '(' | |
// 1 -> ')' | |
// Must begin with 0 or '(' to be valid - LSB (EVEN NUMBER) | |
if(x % 2 != 0) { | |
bitStack.push(-1); | |
// break; | |
} | |
else { | |
for(var j=0;j<2*n;j++) { | |
var bit = x % 2; | |
if(j==0 && bit == 1){ | |
bitStack.push(-1); | |
break; | |
} | |
x = Math.floor(x/2); | |
if(bit == 0){ | |
bitStack.push(bit); | |
}else{ | |
if(bitStack[bitStack.length-1] == 0){ | |
bitStack.pop(bit); | |
}else{ | |
bitStack.push(bit); | |
} | |
} | |
debugParColletor+=bit==0?"(":")"; | |
debugBitColletor+=bit; | |
} | |
} | |
if(bitStack.length == 0){ | |
// console.log(debugParColletor); | |
// console.log(debugBitColletor); | |
// console.log(i); | |
// if(i%2!=0){ | |
// console.log("ODD"); | |
// } | |
totalNumberOfCombinations++; | |
} | |
// VERY INEFFICIENT | |
// do { | |
// } while(x > 0) | |
// var paranthesisCombination = ""; | |
// var bnumber = ""; | |
// var pStack = []; | |
// while (bitStack.length > 0) { | |
// var bit = bitStack.pop(); | |
// if(bit==0) | |
// { | |
// pStack.push(bit); | |
// paranthesisCombination += "("; | |
// } | |
// else { | |
// if(pStack[pStack.length-1] == 0){ | |
// pStack.pop(bit); | |
// }else{ | |
// pStack.push(bit); | |
// } | |
// paranthesisCombination += ")"; | |
// } | |
// // if(pStack.length==0 || pStack[pStack.length-1] == bit) { | |
// // pStack.push(bit); | |
// // }else if(pStack[pStack.length-1] != bit){ | |
// // pStack.pop(bit); | |
// // } | |
// bnumber+=bit; | |
// } | |
// if(pStack.length == 0){ | |
// console.log(paranthesisCombination); | |
// console.log(bnumber); | |
// } | |
} | |
console.log(totalNumberOfCombinations) | |
} | |
//NODE JS | |
//node numberOfValidParenthesesCombinationsOfN.js 8 | |
// const args = process.argv.slice(2) | |
// console.time('getNumberOfValidParenthesesCombinationsOfN'); | |
// getNumberOfValidParenthesesCombinationsOfN(args[0]); | |
// console.timeEnd('getNumberOfValidParenthesesCombinationsOfN'); | |
//ANY JS RUNTIME | |
getNumberOfValidParenthesesCombinationsOfN(8) | |
// 2 | |
// ()() | |
// (()) | |
// 1 | |
// () | |
// 111111 | |
// 1+2+4+8+16+32 | |
// 3 | |
// ( ( () ) ) | |
// () () () | |
// (()) () | |
// () (()) | |
// ( () () ) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment