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

Random Pointer Reversal

Consider a Linked List with each Node, in addition to having a 'next' pointer also has a 'random' pointer. The 'random' pointer points to some random other Node on the linked list. It may also point to NULL. To simplify things, no two 'random' pointers will point to the same node, but more than 1 Node's random pointer can point to NULL.
Now we are required to reverse the direction of all the pointers (both the 'next' and 'random') of the Linked list. The constraint is the solution MUST be O(1) space complexity (A constant number of new nodes can be created but not proportional to the length of the list)

Solution :

Please refer to the following link for suitable answer :
http://stackoverflow.com/questions/8410714/reversing-a-linkedlist-with-nodes-having-a-random-pointer

Occurrence Count

Given a sorted array input[] of size N with possible duplicate integer elements. Devise an algorithm to find out the count of occurrences of a given number K.
Expected time complexity : O(log N)

Ex [1 3 3 4 4 4 4 4 5 5 6 6 7] K=4
Answer = 5

Solution :

We find first occurrence and last occurrence using binary search.
Then occurrence count would be the difference plus one.

Code :

int bin_search_first_occur(int *a,int low,int high,int data)
{
    int mid;
    while(high>=low)
    {
        mid=(low+high)/2;
        if((a[mid]==data && mid==low) || (a[mid]==data && a[mid-1]<data))
            return mid;
        else if(a[mid]>=data)
            high=mid-1;
        else
            low=mid+1;
    }
    return -1;
}
int bin_search_last_occur(int *a,int low,int high,int data)
{
    int mid;
    while(high>=low)
    {
        mid=(low+high)/2;
        if((a[mid]==data && mid==high) || (a[mid]==data && a[mid+1]>data))
            return mid;
        else if(a[mid]<=data)
            low=mid+1;
        else
            high=mid-1;
    }
    return -1;
}

int occurrence_count(int []input, int N, int K){

return bin_search_last_occur(input, 0, N-1, K) - bin_search_first_occur(input, 0, N-1, K) + 1;

}

Complexity :

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