Finding smallest symmetric binary roots of a number

Question

An integer obtained by reversing bits of a given integer A is denoted as bit-rev(A). For example, bit-rev(25) = 19, because binary represenation of 25 is 11001 and after reversing it becomes 10011, i.e. 19. Furthermore, bit-rev(26) = 11 and bit-rev(11) = 13. A symmetric binary root of a given positive integer N is a positive integer A such that N=A*bit-rev(A). For example symmetric binary root of 50 is 10, because 10*bit-rev(10)=10*5=50 . Note that 5 is not a symmetric binary root of 50. Number 286 has two symmetric binary roots: 22 and 26. Write a function

int symmetric_binary_root_count(in​t n)

that given a positive integer N returns the smallest symmetric binary root of N. The function should return -1 if N doesn't have any symmetric binary root. Assume that 0

If you like you can use this function for bit-rev (JavaScript):

function bit_rev(n){
var x = n.toString(2).toString(),
arr = [];
for(var i = 0; i< x.length; i++){ arr.push(x.substr(i,1));}
x = arr.reverse().join('');
return parseInt(x,2);
}

Answer 1

Scala:

def bitrev (n: Int) =
  Integer.parseInt (n.toBinaryString.reverse, 2)

def symmetricBinaryRootCount (n: Int) =
  (1 to n).find (i=> i * bitrev (i) == n)

def sbrc (n: Int) =
  symmetricBinaryRootCount (n) match {
    case Some (n: Int) => n
    case None          => -1 
  }

sbrc (50)
sbrc (286)

results in 10, 22. Pretty straight forward. No golfing?

update, explaining the code.

sbrc (50) is the invocation - result is 10. sbrc (50) calls the so named method (def ...) above, which takes an int, and passes it to symmetricBinaryRootCount. The result is matched against two cases, Some (Int) or None, which are the result of find (which we will see later).

Scala has a Type Option, which is parametric, like List or Array, so you can have an Option [Int] or an Option[Array[String]] and so on. The content of the Option is either None or Some - Some Int, Some Array of String. In other languages the name is Maybe, and the purpose is, to avoid NullPointerExceptions.

So depending on the result, we return the result or we return -1, if there is no result. The result is produced by this method:

def symmetricBinaryRootCount (n: Int) =
  (1 to n).find (i=> i * bitrev (i) == n)

(1 to n) is simply the range of 1 to n. In this range find something, which is a true expression.
find iterates over the range, and tries 1, 2, 3, ... as i in the expression (i * bitrev (i) == n).

And bitrev is made from library methods and implicit conversions:

Integer.parseInt (n.toBinaryString.reverse, 2)

10.toBinaryString is "1010".
"1010"reverse is "0101"
Integer.parseInt ("0101", 2) parses the input as Base-2 encoded String.

So bitrev(10) is 5, and 10 * bitrev(10) = 50 will be the first solution found in (1 to 50).

Find operates lazy, that means it will stop after finding a result and not probing teh values from 11 to 50.

And here is a pre-golfed one-liner:

def sbrc (n: Int) = (1 to n).find (i=> i * Integer.parseInt (i.toBinaryString.reverse, 2) == n) getOrElse (-1)

Answer 2

C Sharp

int b(int c) { for(var i=0;i<c;i++) if(a(i)*i==c) return i; return -1;}
int a(int b) { return Convert.ToInt32(new string(Convert.ToString(b,2).Reverse().ToArray()), 2);}

Answer 3

Javascript, 117 characters

function f(n,i){for(i=0;i<=n;++i)if(n==i*parseInt((i).toString(2).split("").reverse().join(""),2))return i;return -1}