# Parenthifiable Binary Numbers

If you express some positive integer in binary with no leading zeros and replace every 1 with a ( and every 0 with a ), then will all the parentheses match?

In most cases they won't. For example, 9 is 1001 in binary, which becomes ())(, where only the first two parentheses match.

But sometimes they will match. For example, 44 is 101100 in binary, which becomes ()(()), where all the left parentheses have a matching right parenthesis.

Write a program or function that takes in a positive base ten integer and prints or returns a truthy value if the binary-parentheses version of the number has all matching parentheses. If it doesn't, print or return a falsy value.

The shortest code in bytes wins.

Related OEIS sequence.

Truthy examples below 100:

2, 10, 12, 42, 44, 50, 52, 56


Falsy examples below 100:

1, 3, 4, 5, 6, 7, 8, 9, 11, 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, 43, 45, 46, 47, 48, 49, 51, 53, 54, 55, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99

• More OEIS
– user45941
Nov 16, 2015 at 3:44
• There's a sequence for everything... Nov 16, 2015 at 4:38

# Husk, 8 bytes

¬ωoσḋ2øḋ


## Lua (96 bytes)

function g(n)function f(m)return m>0 and f(m//2)..m%2 or""end return f(n):gsub("%b10","")==""end


# K (ngn/k), 22 18 bytes

-4 bytes by making things tacit

~#(""/"10"\)/,/$2\  Try it online! • 2\ convert (implicit) input integer to base-2 representation • ,/$ convert the base-2 representation to a string
• (""/"10"\)/ run a converge-/, splitting on instances of "10", joining with "" (in effect replacing instances of "10" with "")
• ~# check if there are any unmatched parentheses left

# AWK, 56 bytes

{for(a=$++b;a;a=int(a/2))(d+=a%2?-1:1)<0?b=0:0}1,$0=b*!d


Try it online!

The general idea here is the code runs through all the binary bits of the number, from the least significant digit to the most significant digit. At each point the parenthetical "depth" is calculated. The result is truthy if the final depth after all the digits have been considered is 0 and as long as intermediate depth is never negative.

 for(a=$++b;a;a=int(a/2))  This loop processes each bit. The initialization a=$++b is just a golfed version of a=$1; b=1 setting a to the number requested and the default result "are all interim depths OK" variable b to 1. It stops when all the bits have been process, which is when a is falsy. And the end of loop shifts the number we're working down on bit with a=int(a/2) since I can't think of a short way to do integer math in AWK...  (d+=a%2?-1:1)<0?b=0:0  The body of the loop is just one statement. It either increments of decrements the "depth count" variable depending on whether or not the current bit is set using d+=a%2?-1:1. And then it sets the "does the depth ever go negative" variable b to 0 if the depth dips below zero with, which is this part of the statement (...)<0?b=0:0. One we've run through all the bits, the only thing left is to decide if the number met the two success factors for the test,  1,$0=b*!d


If both tests pass, then b*!d will be 1. Setting $0 to that means AWK will print 1 or 0 since the 1, bit at the front means the test will always evaluate to true. # 05AB1E, 6 bytes bTõ:õQ  Explanation: b # Convert the (implicit) input-integer to a binary-string Tõ: # Keep replacing 10 with "" as long as it's possible õQ # Check if what remains is an empty string "" # (after which the result is output implicitly)  # Java (JDK), 56 bytes Not an innovative solution, but the previous Java answer really needed an outgolfing. It converts the integer parameter in binary classically (using modulo and division by 2), and since we are converting from right to left, it considers 0 as a +1 and 1 as a -1 in a score variable. The score gets "stuck" forever at -1 if it ever reaches this value (if a ( is encountered before having encountered its matching )), or can increase indefinitely if there are too many ) without their matching (. So at the end, the only acceptable score is 0 if the binary is perfectly "balanced". n->{int r=0;for(;n>0;n/=2)r+=r<0?0:1-n%2*2;return r==0;}  Try it online! Really close alternative solution using inline Stream (61 bytes, requires an Integer as parameter for the trick of calling the static toString on n, which wouldn't work with a primitive int) : n->n.toString(n,2).chars().reduce(0,(a,b)->a<0?a:a+b*2-97)==0  # Thunno 2, 6 bytes )(BøB  #### Explanation )(BøB # Implicit input )( # Two character string ")(" B # Convert input to base ")(" øB # Are the brackets balanced? # Implicit output  #### Screenshot # Scala, 82 bytes Golfed version. Try it online! i=>{var b=i.toBinaryString;while(b.contains("10"))b=b.replaceFirst("10","");b<"0"}  Ungolfed version. Try it online! object Main { def main(args: Array[String]): Unit = { (1 until 100).filter(x => isBinaryWithout10(x)).foreach(x=>println(s"$x true"))
}

def isBinaryWithout10(i: Int): Boolean = {
var binary = i.toBinaryString
while (binary.contains("10")) {
binary = binary.replaceFirst("10", "")
}
binary < "0"
}
}



## C# 98 bytes

bool f(int m){int i=0;foreach(char s in Convert.ToString((m),2)){if(s=='1')i+=2;i--;}return i==0;}


open for any suggestions. i like this challange even tho it is old-ish

# Nekomata + -e, 7 bytes

Ƃ£E∫Ɔž≥


Attempt This Online!

Ƃ£E∫Ɔž≥
Ƃ           Convert to base-2
£E         Power of -1
∫        Cumsum
Ɔ       Split into the initial part and the tail
ž      Check if the tail is zero
≥     Check if the initial part is greater than or equal to the tail
`