Integer Binary Roots

An integer obtained by reversing the bits of a given integer A is denoted as bit-rev(A). For example, bit-rev(25) = 19, because the 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, a 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. The number 286 has two symmetric binary roots: 22 and 26.

Write a function int symmetric_binary_root_count(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 N is an integer within the range [1 ... 2,147,483,647].

For example, given N = 3245 the function should return 55.

Expected Complexities:

• worst-case time complexity is O(sqrt(N));
• worst-case space complexity is O(1).

Solution :

This problem is just integer factorization made more complicated. For a given natural number N, the problem is to determine the set of pairs of divisors (A, N / A) satisfying the predicate bit-rev(A) = N / A or bit-rev(N / A) = A.

The simplest algorithm of calculating pairs of divisors (A, N / A) is to begin with 1 and trial divide N by the counter value, up to floor(sqrt(N)). Calculating the bit-rev is O(1) because there are a finite number of bits in an integer represented on a computer. So, the process is O(sqrt(N)).

Code :

unsigned bit_rev(unsigned N){

unsigned result=0, i;
int max = sizeof(unsigned) * CHAR_BIT;

for (i = 0; i < max; ++i) {

result |= (((N >> i) & 0x1) << (max - i - 1));

}

return result;

}

unsigned smallest_integer_binary_root(unsigned N){

unsigned result = 0, i;
unsigned sq = ceil(sqrt(N));

for(i=1; i<sq; i++){

if(N%i == 0){

if(bit_rev(i) == N/i)

return i;

elseif(bit_rev(N/i) == i)

result = N/i;

}

}

return result;

}

Complexity :

• Time : O(sqrt(N))
• Space : O(1)

Reference :http://stackoverflow.com/questions/8465519/binary-roots-of-an-integer