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)

Largest 100

There is a big file containing 10^8 integers, one per line. Devise an algorithm to find the largest 100 integers among them. Remember you cannot read all of them into memory at once.

Solution :

We simply use Min-Heap data structure to keep list of top 100 numbers replacing next with lowest if greater.

Code :

/**
 *  Assume standard heap ADT operations : heap_min(), heap_remove() and heap_insert()
**/

void top_100(FILE *fp, int output[]){

int num, count=0;

while(fscanf(fp, "%d\n", &num)){

if(++count > 100 && num > heap_min(output)){

heap_remove(output);

}
heap_insert(output, num);

}

}

Complexity :

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

Bitonic array

Given an array of N distinct integers with the property that there exists an index K (0 <= K <= N-1) such that input[0], ..., input[K] is and increasing sequence and input[K], ..., input[N-1] is a decreasing sequence. Devise and algorithm to find K.

Ex [1 2 4 7 10 15 13 11 5 0 -5]
Answer: K=5 (input[K]=15)

Solution :

Use binary search with the following conditions :

input[mid-1] < input[mid] > input[mid+1] for mid != 0 and mid != N-1
input[mid] > input[mid+1]  for mid == 0
input[mid-1] < input[mid] for mid == N-1

with initial low = 0, high = N-1, mid = (high + low)/2

Code :

int bitonic_pivot(int input[], int N)
{

    int low=0, high=N-1, mid;

    while(low < high)
    {

        mid=(low+high)/2;

        if((!mid || (input[mid-1] < input[mid])) && (mid != N-1 || (input[mid] > input[mid+1])))

            return mid;

        else if((!mid || (input[mid-1] < input[mid])) && (mid != N-1 || (input[mid] < input[mid+1])))

            low=mid+1;

        else if((!mid || (input[mid-1] > input[mid])) && (mid != N-1 || (input[mid] > input[mid+1])))

            high=mid;

    }

    return -1;

}

Complexity :

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

Largest Non Consecutive Subsequence

Given a sequence of N integers, devise an algorithm to find a sub-sequence S[] for which sum of its elements is maximum and such that S contains no two consecutive elements from input sequence.

Ex. input[] = [1 5 3 7 -2 -4 2]
Answer [5 7 2] Sum=14

Solution :

This requires Dynamic Programming formulation :
Let sum[i] represent maximum non-consecutive subsequence sum till ith element of input[], then
sum[i] = max(sum[i-1], input[i] + sum[i-2])

which says that new sum would either be obtained by not including ith element i.e previous sum, or by including it with last to previous sum i.e input[i-2]. The new sum would be maximum of these two possibilities.

Code :

int largest_non_consecutive(int input[], int N, int output[]){

int sum[N], jump[N], k=0, i;

sum[0] = input[0];
jump[0] = -2

if(input[1] > input[0]){

sum[1] =  input[1];
jump[1] = -1;

}
else {

sum[1] =  input[0];
jump[1] = 0;

}

for(i=2; i<N; i++){

if(sum[i-1] > input[i] + sum[i-2])){

sum[i] =  sum[i-1];
jump[i] = i-1;

}
else {

sum[i] = input[i] + sum[i-2];
// input[i] is included in resulting sequence when jump[i] is i-2
jump[i] = i-2;

}

}

// fill output according to jumps -- resulting sequence is in reverse order
for(i=N-1; i; i++){

if(jump[i] == i-2){

output[k++] = input[i];

}

}

return sum[N-1];

}

Complexity :

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

Adjacent removal

Given a string. Write an algorithm to remove adjacent characters if they are same.

Ex. Input = abccbcba
remove cc => abbcba
remove bb => acba (final result)

Solution :

We just compare the last element with next and if equal remove both.
[In implementation we may also use stack]

Code :

// M = output size

void adjacent_removal(int input[], int N, int output[], int *M){

int i=1;
*M = 0

while(i < N){

while(input[i] == input[*M] && (i < N) && (*M >= 0)){

i++;
(*M)--;

}
output[++(*M)] = input[i];

}

}

Complexity :

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

Lonely element

Given an array of integers with size 2N+1 such that N elements appear twice in arbitrary positions and 1 element appears only once.
Devise an algorithm to find the lonely element.

Ex : {1 2 4 5 1 4 2}
Answer : 5

Solution :

Note the properties of XOR :

1. A ^ A = 0
2. 0 ^ A = A
3. A ^ (B ^ C) = (A ^ B) ^ C

Thus we just XOR all integers to finally get the lonely element since all others will be made 0 for repeating twice.

Complexity :

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

Code :

int lonely_element(int input[], int N){

int result=0, i=0;

for(i=0; i<N; i++)

result ^= input[i];

return result;

}

Check range

Write a function that takes an int array of size M, and returns (true/false) if the array consists of the numbers only within the range [N, N+M-1]. The array is not guaranteed to be sorted.
For instance, {2,3,4} would return true. {1,3,1} would return true, {1,2,4} would return false.

Solution :

Simply find out the maximum and minimum in one pass and check if N == (max - min + 1)

Complexity :

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

Code :

int check_range(int input[], int N){

int max = input[0], min = input[0], i;

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

if(input[i] < min) min=input[i];
if(input[i] > max) max=input[i];

}

return (max - min + 1) == N;

}

Find repeated element

Given an array of size N which contains all the numbers from 1 to N-1. Find the number which is repeated in O(N) time.
How do you proceed with the same with floating numbers from 0 to 1 instead of 1 to N-1 ?

Solution :

For integers use sum to find the repeated number.
For floating numbers, use Hash tables.

Complexity :

• Time : O(N)
• Space : O(1) [O(K), K >> N for hash table]

Code :

int repetition_int(int input[], int N){

int i=0, sum=0;

for(i=0; i<N; i++)

sum += input[i];

return sum - (N*(N-1)/2);

}

float repetition_float(float input[], int N){

int i;

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

if(hash_table_exists(input[i]))

return input[i];

hash_table_insert(input[i]);

}

return -1.0;

}

Tricky addition

Write a function to add to integers without using mathematical operators (+, -, *, /, ^).

Solution :

We use the logic used in digital circuits where sum = A XOR B and carry = A AND B. We simply add the carry again after shifting it 1 left till it become zero.

Complexity :

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

Code :

int add(int a, int b){

int carry = 0;
while(b){

carry = a & b;
a = a ^ b;
b = carry << 1;

}
return a;

}

Largest subsequence in terms of absolute sum

Given an array of N integers (both positive and negative), find the sub-sequence with largest absolute sum.
For ex: Let A = {1 2 -5 4 5 -1 2 -11} then largest absolute sum is 11 with sub-sequence {-11}.

Solution :

A simpler variant was previously discussed [Largest consecutive sum], here the difference being absolute sum.
We use the same algorithm of O(N) here too first to get highest positive sum and then highest negative sum and find the one with higher absolute value as the answer.

Complexity :

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

Code :

void largest_consecutive_sum(int input[], int N, int *start, int *end, int *max){

*start = *end = *max = -1;
int current = -1;
int sum = 0;

for(int i=0; i<N; i++){

sum += input[i];

if(sum < 0){

sum = 0;
current = i+1;

}

if(sum > *max){

*max = sum;
*start = current;
*end = i;

}

}

}

void largest_consecutive_absolute_

sum(int input[], int N, int *start, int *end, int *max){

int pos_start, pos_end, pos_max, neg_start, neg_end, neg_max;
int i;

largest_consecutive_sum(input, N, &pos_start, &pos_end, &pos_max);

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

input[i] = -1*input[i];

}

largest_consecutive_sum(input, N, &neg_start, &neg_end, &neg_max);

if(pos_max > neg_max){

*start = pos_start;
*end = pos_end;
*max = pos_max;

}
else {

*start = neg_start;
*end = neg_end;
*max = neg_max;

}

}

Modified 2-color sort

Given an array of integers containing only 0s and 1s.You have to place all the 0s in even position and 1s in odd position. And if suppose, no. of 0s exceed no. of 1s or vice versa then keep the exceeding integers untouched. Do that in ONE PASS and without taking extra memory (modify the array in-place).

For Example :
Input Array:    [0,1,1,0,1,0,1,0,1,1,1,0,0,1,0,1,1]

Output Array: [0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1]

Solution :

Find the wrong positions for 0 and 1 and swap them

Complexity :

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

Code :

void interleave_0_1(int input[], int N){

int i=0, j=1;

while(1){

while(i < N && input[i] == 0)

i += 2;

while(j < N && input[j] == 1)

j += 2;

if(i < N && j < N){

input[i] ^= input[j];
input[j] ^= input[i];
input[i] ^= input[j];

}
else

break;

}

}

Reversing linked list

Devise an algorithm to print elements of linked list in reverse without reversing the linked list. State the time and space complexities.

Solution :

Use recursion

Complexity :

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

Code :

void display_reverse(node *list){

       if(list){

              display_reverse(list->next);

              printf("%d\n", list->info);

       }

}

Largest sum of elements with no three consecutive

Given a sequence of  positive numbers, find the maximum sum that can be formed which has no 3 consecutive elements present.

For example: consider the sequence 3000 2000 1000 3 10  Here,  the answer would be 5013, by taking 3000, 2000, 3 & 10. Note that we can't form a sequence that takes 3000, 2000 & 1000 together because they are the consecutive elements of the array.

Sample cases 1 2 3                            ans=5 

100 1000 100 1000 1                        ans=2101 

1 1 1 1 1                                            ans=4 

1 2 3 4 5 6 7 8                                   ans=27

Try to find an O(N) solution. N is the number of elements in the array. 

Solution :

The solution for this problem is by dynamic programing as given below in code.

Complexity :

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

Code :

int max_three(int[] input, int N){

int sum[] = new int[N+2];

sum[0] = 0;

sum[1] = input[0];

sum[2] = input[0] + input[1];

for (int i=2; i<N ;++i){

    sum[i+1] = max(input[i] + sum[i-1], input[i] + input[i-1] + sum[i-2]);

    sum[i+1] = max(sum[i+1], sum[i]);

}

return sum[N];

}

Zero the matrix

Given a N x N matrix with 0s and 1s. Devise an algorithm such that whenever you encounter a 0 make the corresponding row and column elements 0.

Eg.
Input  
1 0 1 1 0
1 1 1 1 1
1 1 1 1 0
1 1 1 1 1
0 0 1 1 0

Output
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0

Solution :

We keep two arrays for rows and columns with 0 indicating the corresponding row/column contains at least one 0.
Finally we use these arrays to set the required cells to 0.

Complexity :

• Time : O(N^2)
• Space : O(N)

Code :

void matrix_set_zero(int *input, int N){

int *row = new int[N];
int *col = new int[N];

for(int i=0; i<N; i++){

row[i] = col[i] = 1;

}

for(int i=0; i<N; i++){

for(int j=0; j<N; j++){

row[i] &= input[i][j];
col[j] &= input[i][j];

}

}

for(int i=0; i<N; i++){

for(int j=0; j<N; j++){

input[i][j] = row[i] & col[j];

}

}

}

Kth smallest in union of arrays

Given two sorted arrays of size M and N. Find Kth smallest element in the union of the two arrays in constant space. (i.e. without using additional space).

Solution :

The Kth element will be found within first K elements of both arrays, so we consider only these elements or whole array if size is less than K
We use recursive procedure. We compare (K/2)th element in arrays A(0 K) and B(0 K)
if A(K/2) < B(K/2) we recursively find (K-K/2)th smallest element in A(K/2+1 K) and B(0 K/2) eliminating first K/2 elements from A
else if A(K/2) > B(K/2) we recursively find (K-K/2)th smallest element in B(K/2+1 K) and A(0 K/2) eliminating first K/2 elements from B
if A(K/2) == B(K/2) return A(K/2) as answer

Boundaries must be checked in the procedure

Complexity :

• Time : log N + log M (Please check if its min(log N, log M) rather than this)
• Space : O(1)

Code :

void kth_smallest(int[] A, int M, int[] B, int N, int K, int &result){

int a_high = (M < K) ? M : K;
int b_high = (N < K) ? N : K;

result = find_kth(A, 0, a_high, B, 0, b_high, K);

}

int find_kth(int[] A, int a_low, int a_high, int[] B, int b_low, int b_high, int K){

// boundary cases
if(a_low > a_high)

return B[b_low + K - 1];

if(b_low > b_high)

return A[a_low + K - 1];

int mid = (K+1)/2;  // finding ceiling of K/2

if(A[mid] == B[mid])

return A[mid];

else if(A[mid] < B[mid])

return find_kth(A, a_low + mid+1, a_high, B, b_low, b_low + mid, mid);

else if(A[mid] > B[mid])

return find_kth(A, a_low, a_low + mid, B, b_low + mid + 1, b_high, mid);

}

void kth_smallest_linear(int[] A, int M, int[] B, int N, int K, int &result){

int i=0, j=0;
for( ; K; K--){

if(i >= M){

result = B[j + K - 1];
break;

}
if(j >= N){

result = A[i + K - 1];
break;

}
if(A[i] == B[j]){

result = A[i++];
j++;

}
else

result = (A[i] < B[j]) ? A[i++] : B[j++];

}

}

Last non-zero digit of N!

Find the last non-zero digit of N!. Assume N! to be extremely large.

Solution : 

Please refer the following link for an in-depth analysis of solutions to this problem :
http://comeoncodeon.wordpress.com/2009/06/20/lastnon-zero-digit-of-factorial/

Run length encoding

Run-length encoding (RLE) is a very simple form of data compression in which runs of data (that is, sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original run. Count of 1 is not indicated. Write a program to find RLE of given string.

Eg.
input = "aabbbcddeef" RLE = "a2b3cd2e2f"
input = "aaabbcddeeeef" RLE = "a3b2cd2e4f"

Solution :

We simply use a switch while checking each character in input and count them if equal and print the count if count is greater than one.

Complexity :

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

Code :
void rle_encode(char[] input, int N, char[] output){

int index = 0, count = 1;
char last = input[0];

for(int i=1; input[i]; i++){

if(last == input[i]){

count++;

}
else {

output[index++] = last;
if(count > 1){

output[index++] = count + '0';
count = 1;

}
last = input[i];

}

}

output[index++] = last;
if(count > 1){

output[index++] = count + '0';

}

}

Existence of closed chain of words

You are given a set of words. A chain is formed by joining words W1 and W2 such that last character of W1 is first character of W2. Devise an algorithm to check whether such a closed chain that uses all words in the set exists for given set of words.

Eg.
S = { abc, gha, efg, cde }
Exists : abc-cde-efg-gha

Solution :

The answer to this question is to find existence of Euler circuit in the graph formed by the 26 possible vertices a-z and words being directed edges. We check the following conditions for existence of Euler circuit :

1. the graph is connected
2. incoming edges count equals outgoing edges count for each vertex

Code :

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define toNumber(character) (character-97)

int alpha[26][26];
int occur[26], found[26];

typedef struct tList{
    int val;
    struct tList *next;
} *list;

int connected(){
    int i, root;
    int Q[26], color[26], head = 0, tail = -1;

    for( i=0; i<26; i++ ){
        color[i] = 1;
        if( found[i] == 1 ){
            root = i;
            color[i] = -1;
        }
    }

    Q[++tail] = root;

    while( tail >= head ){
        int u = Q[head++];
        color[u] = 1;
        for( i=0; i<26; i++ )
            if( color[i] == -1 && alpha[u][i] == 1 ){
                Q[++tail] = i;
                color[i] = 0;
            }
    }

    for( i=0; i<26; i++ )
        if( color[i] != 1 )
            return 0;

    return 1;
}

int checkEvenDegree(){
    int i;

    for( i=0; i<26; i++ )
        if( occur[i] != 0 )
            return 0;

    return 1;
}

void performTest(){
    int i, j, num;
    scanf( "%d", &num );

    for( i=0; i<26; i++ ){
        occur[i] = 0;
        found[i] = 0;
        for( j=0; j<26; j++ )
            alpha[i][j] = 0;
    }


    char word[1001];

    for( i=0; i<num; i++ ){
        scanf( "%s", word );

        int len = strlen( word );

        found[ toNumber(word[0]) ] = 1;
        found[ toNumber(word[strlen(word)-1]) ] = 1;

        occur[ toNumber(word[0]) ]--;
        occur[ toNumber(word[strlen(word)-1]) ]++;

        alpha[ toNumber(word[0]) ][ toNumber(word[strlen(word)-1]) ] = 1;
    }

    if( checkEvenDegree() && connected() ){
        printf( "Ordering is possible.\n" );
        return;
    }

    printf( "Ordering not possible.\n" );
    return;

}

int main(){
    int numTest;
    scanf( "%d", &numTest );

    while( numTest-- )
        performTest();

    return 0;
}

Acknowledgments :

Abhishek Kumar (abhishek.kumar.cse08@itbhu.ac.in)

Next integer with same number of set bits

Given an integer N. Devise an algorithm to find out the smallest integer greater than N having the same number of bits set as that of N. (When a bit is 1, we say it is set)

Eg.
N = 10 (1010)
Next = 12 (1100)

Solution :

1. Suppose N has last x bits 0 and then y bits 1, then in general the next number having same number of set bits is given by N + 2^(y-1) + 2^x - 1
2. Now 2^x is given by N&-N
3. Suppose M = N + 2^x
4. Similarly 2^(x+y) is given by M&-M
5. So we get 2^(y-1) by (2^(x+y)/2^x >> 1)

Complexity :

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

Code :

int next_equal_setbits(int N){

int K1 = N & -N; int M = N + K1;
int K2 = M & -M;
return K2 + ((K2/K1)>>1) - 1;

}

Permutations of string

Given a array of characters of size N. Devise an algorithm to generate all possible permutations of given size K (K <= N).

Solution :

1. We first list the combinations using recursive procedure by selecting or not selecting characters until K length has been formed
2. The for each combination we permute them using another recursive procedure

Complexity :

• Time : O(N!)
• Space : O(N!) when storing results O(1) if directly output the result

Code :

void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

void select(char *input, int start, int N, char *selection, int length, int K, stack<string> &combinations){
    if(start <= N){
        if(length == K){
            selection[length] = '\0';
            combinations.push(string(

selection));
        }
        else {
            select(input, start + 1, N, selection, length, K, combinations);
            selection[length] = input[start];
            select(input, start + 1, N, selection, length + 1, K, combinations);
        }
    }
}

void permute(char *input, int index, int N, stack<string> &permutations)
{
   if (index == N)
        permutations.push(string(input));
   else
   {
        for (int i = index; i < N; i++)
       {
            swap(input + index, input + i);
            permute(input, index + 1, N, permutations);
            swap(input + index, input + i);
        }
   }
}

void all_permutations(char *input, int K, stack<string> &permutations){
    int N = strlen(input);
    stack<string> combinations;
    char *selection = new char[K+1];
    char *temp = new char[K+1];
   
    select(input, 0, N, selection, 0, K, combinations);
    while(!combinations.empty()){
        strcpy(temp, combinations.top().c_str());
        permute(temp, 0, K, permutations);
        combinations.pop();
    }
}

Swapping without temporary storage

Give a method to swap two numbers without using additional memory.

Solution :

1. We may use addition/subtraction or XOR to achieve this.
2. XOR does not cause overflows and hence is superior.

Complexity :

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

Code :

void swap_xor(int &num1, int &num2){

num1 ^= num2;
num2 ^= num1;
num1 ^= num2;

}

void swap(int &num1, int &num2){

num1 = num1 + num2;
num2 = num1 - num2;
num1 = num1 - num2;

}

Quickly multiply with 7

Give a fast method to multiply a number by 7.

Solution :

1. We multiply by 7 by first multiplying by 8 and subtracting the number from the result.
2. Multiplication by 8 is equivalent to shifting left 3 bits.

Complexity  :

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

Code  :

int multiply_7(int N){

return (N << 3) - N;

}

Searching in two dimensions

Given 2D array with integers sorted both horizontally and vertically. Devise an efficient algorithm to search for key in the 2D array. What is the complexity ?

Eg.  1 4 7 13
       2 5 9 15
       3 6 10 16

Solution :

Two solutions exists :
(Assume the row is sorted from left to right and column from top to bottom so that the least number is at top-left)

First one is :

1. Start from left-bottom
2. While within boundary
1. If key found print and exit
2. If key is smaller move up else move right

Second one :

1. Let M < N (otherwise interchange the usage below)
2. for each M 1D arrays do binary search in O(log N)

Complexity :

First :

• Time : O(M + N)
• Space : O(1)

Second :

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

The advantage of second method is seen when M << N where second method degenerates to binary search whereas first method degenerates to sequential search.

Code :

/**
 * M rows
 * N columns
 * (row, col) position of searched key if successful
**/

First method :

bool search_2D(int *input, int M, int N, int key, int *row, int *col){

*row = M-1;
*col = 0;

while(*row > 0 && *col < N){

int current = *(input + N*(*row) + (*col));
if(key == current)

return true;

else if(key < current)

(*row)--;

else

(*col)++;

}

return false;

}

Second method :

bool search_2D(int *input, int M, int N, int key, int *row, int *col){

int increment = 1, total_rows = M, total_cols = N;
if(M > N){

increment = N;
total_rows = N;
total_cols = M;

}

for(*row =0; *row < total_rows; i++){

*col = 0;
if(search_1D(input + *row, total_cols, key, col, increment)){

return true;

}

}

return false;

}

bool search_1D(int *input, int N, int key, int *index, int increment){

int low = 0, high = N-1;

while(low <= high){

*index = (low + high)/2;
int value = *(input + (*index)*(increment));

if(value == key)

return true;

else if (value < key)

low = *index + 1;

else

high = *index - 1;

}

return false;

}

Difference of powers of 2

Devise an algorithm to find whether a given positive number N is of the form 2^x - 2^y (^ means exponentiation, x and y are positive and x>y>0).

Solution :

1. We first take OR of N and N-1 to make all right bits 1
2. Then add 1 and use N & N-1 trick to see if result is zero to conclude that N was of the correct form.

Complexities :

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

Code :

bool check_form(int N){

if(N < 2) return false;

N = N | N-1;      // better written as N |= N-1;

N++;
return N & N-1;

}

Min-Max Stack

Assume you have infinite memory. Design a algorithm using stacks that can find the minimum and maximum at any point while reading an infinite sequence of numbers in least possible time.

Eg. 5, 9, 2, 35, 23, 1, ...
After 3rd element, the algorithm would tell min = 2, max = 9
After 6th element, algorithm would tell min = 1, max = 35

Solution 1 :

Since there is no limitation on space, so we can maintain 3 stacks.

• 1st stack will be the main stack in which we are pushing all elements
• 2nd stack will contain maximum elements up to that point
• 3rd stack will contain minimum elements up to that point.

So range can also be found in O(1) time, by popping from 2nd stack & 3rd stack and taking their difference.

Complexities :

• Time : O(1)
• Space : Unlimited

Code :

template <class T>
class range_stack<T> {

private :

stack<T> main, min, max;

public :

int push(T value){

main.push(value);

if(main.empty()){

min.push(value);
max.push(value);

}
else {

if(min.top() > value)

min.push(value);

else

min.push(min.top());

if(max.top() < value)

max.push(value);

else

max.push(max.top());

}

}

T pop(){

T tmp = main.top();
main.pop();
min.pop();
max.pop();
return tmp;

}

T range(){

return max.top() - min.top();

}

}

Check non-existence of number

Devise an algorithm to determine non existence of a number in a sorted list of N numbers where the numbers range over M, M >> N and N large enough to span multiple disks (You may read one number at a time from the list but it will not be possible to store all of them in the memory).

Solution :

1. The solution is using bitmaps (arrays of bits)
2. Initialization will take O(N) but checking for existence will be done in O(1)
3. Bitmap array will be char[M/8] since a char is 8 bits long

Complexities :

• Time : O(N) in initialization, O(1) in access
• Space : O(M)

Code :
// init() is called once for all numbers in list one by one to initialize the bitmap

void init(int[] bitmap, int M, int num){

int base = num/8;
int offset = 1 << (n%8);
bitmap[base] |= offset;

}

bool exists(int[] bitmap, int M, int num){

int base = num/8;
int offset = 1 << (n%8);
return (bitmap[base] & offset);

}

Sum of powers of 2

Devise an algorithm to find whether a given number N is of the form 2^x + 2^y (^ means exponentiation, x and y are positive).

Solution :

1. The rightmost bit may be set to zero by (N & N-1), so we do it twice and if the number becomes zero, it means it had 2 bits as 1 before thus having the required form 2^x + 2^y

Complexities :

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

Code :

bool check_form(int N){

if(N < 2)

return false;

N = N & (N-1);

if(!N)

return true;

return (N & (N-1));

}

Random selection

There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random.
Conditions :

1. Use random number function rand() that returns a number between 0 and 1
2. It must be done in O(N) time

Solution :

1. Take 2 arrays R[K] and Num[K]
2. For each element in sorted array read one by one and do :
1. Generate a random number r
2. If R is not full, insert r into R and element into Num array else replace r with highest random number in R and insert current element into corresponding index in Num array (Note that we want to keep the least K random numbers and corresponding elements in list)
3. Print Num[]

Complexities :

• Time : O(N)
• Space : O(K)

Code :

void random_selection(int[] input, int N, int K){

int number[K];
double random[K];
int count = 0;

for(int i=0; i<N; i++){

double r = rand();

    if(r < number[count-1]){

index = insert(random, K, &count, r);

number[index] = input[i];

              }

}

for(int i=0; i<K; i++){

printf("%d ", number[i]);

}

}

int insert(double *list, int K, int *count, double entry){

if(*count == K-1){

(*count)--;

}

int i = *count;
while(*(list+i) > entry){

*(list + i + 1) = *(list + 1);
i--;

}

*(list + i + 1) = entry;
(*count)++;

return i+1;

}

Product Array

There is an array A[N] of N numbers. A Product Array P[N] of an array A[N] is defined such that for all i<N, P[i] = (product of all elements of A except A[i]).

 
For example, P[0] will be multiplication of A[1] to A[N-1] and P[1] will be multiplication of A[0] and from A[2] to A[N-1].

 
Solve this without using division operator and in O(N) time.

Solution :

1. Calculate backward product in product array P[i] = Product(A[i+1]*...*A[N])
2. Take a variable p=1
3. For each element of input, multiply it by p and multiply P[i] by p

Complexities :

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

Code :

void product_array(int[] input, int[] product, int N){

product[N-1] = 1;

for(int i=N-1; i>-1; i++){

product[i] = product[i+1]*input[i+1];

}

int p = 1;
for(int i=0; i<N; i++){

if(i > 0){

p *= input[i-1];

}

product[i] *= p;

}

}

Common node in linked lists

Given the heads of two linked lists, find whether they have any common node. If yes, find the common node.
Try to solve it as elegantly as possible.

Solution:

1. Subtract the length of smaller list from the larger one.
   
2. Move a pointer ahead on larger list by the difference of lengths.
   
3. Now put a pointer on head of smaller list.
   
4. More two pointers together.
   
5. The point at which they meet is the point where they short.

Code : 

Node *getShortedNode(Node *list1, Node *list2){

int d = length(list1) - length(list2);

if(d < 0){

d = d * (-1);
Node *tmp = list1;
list1 = list2;
list2 = tmp;

}

Node *ptr1 = list1;
for(int i=0; i<d; i++){

ptr1 = ptr->next;

}

Node *ptr2 = list2;
while(ptr1 != NULL){

if(ptr1 == ptr2)

break;

ptr1 = ptr1->next;
ptr2 = ptr2->next;

}

return ptr1;

}

int length(Node *list){

int count = 0;
while(list != NULL){

list = list->next;
count++;

}
return count;

}

Complexity :

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

Majority Element

Majority Element is an element of an array that occurs more than half the number of times in the array.

Easy Problem:
Assume that an integer array A[1..n] has a majority element and elements other than majority element are distinct. How to find majority element. What's the space and time complexity of the algorithm ?

Hard Problem:
Assume that an integer array A[1..n] has a majority element and elements other than majority element need NOT be distinct. How to find majority element. What's the space and time complexity of the algorithm ?

Both easy and hard may be solved using the following solution in ~(n-1) comparisons.

Solution (HARD) :
This algorithm uses an observation that if we consider our array to be list of voters and array value is the candidate to whom they are voting, then majority element is the winning candidate.
Additionally, if all other candidates are merged to form one candidate then still it will fail to defeat the majority element candidate (hence the name majority element).
So we can think of it this way. Assuming a negative vote decrease the count of majority element then still the count of majority element would be atleast 1.

int majority_hard(int[] input, int n){

int element = input[0];
int votes = 1;

for(int i=1; i<n; i++){

if(input[i] == element)

votes++;

else if(votes > 0)

votes--;

else {

element = input[i];
votes = 1;

}

}
return element;

}

However, the easy problem may be solved using ~n/2 comparisons using the pigeon hole principle :

Solution (EASY) :
If the total size N is even then, the majority element must duplicate in consecutive positions in some pairs of positions. If N is odd, then it must either duplicate in consecutive positions or must be the last element.

int majority_easy(int[] input, int n){

for(int i=0; i<N; i+=2){

if(input[i] == input[i+1])

return input[i];

}
return input[N];

}

Complexity :

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

Second Minimum Element

Find second smallest element in an array A[1..N] of size N. (We would like to do in much less than 2N comparisons if possible).

Solution :

Finding the smallest element is trivial. The following code would find the smallest element using n-1 comparisons.

min = A[1]
for i = 2 to n
  if A[i] < min 
    min = A[i]
return min

The trivial algorithm to find the second minimum is to keep another variable (smin) along with min and if an element knocks out smin then check if it knocks out min and accordingly do the book-keeping. It can be done using 2n-3 comparisons and takes constant space. 

A point to observe is that the second smallest element is knocked out by the smallest one at some stage. If we preserve which element is knocked out by whom then finding the second smallest element would just require us to find the smallest amongst the elements knocked out by the smallest element.

But in order to do that we need to build the algorithm in a way that we are playing a pair wise tournament. Lets say we play a tournament and knockout n/2 elements after n/2 comparisons. The recurrence relation looks like this: 

T(n) = T(n/2) + n/2

Solving this recurrence gives that T(n) = n - 1. The height of the recurrence tree is lg n. So if we just check these elements knocked by root (min) we get the second minimum.For. E.x.

1   5 2   6  
\ /   \ /  
 1     2
  \   /
    1

As soon as we build the tree using n-1 comparisons, we can check the second largest amongst the number knocked out by 1. i.e. 2, 5. so the second minimum is 2. 

This algorithm can be implemented using an auxiliary array B[1..n]. This tree represents a min heap and can be stored in an array easily. There are many divisions performed (ideally they are right shifts) to index the correct elements, so the actual implementation might look a little complicated.

Another algorithm that is very easy to implement but sadly takes 2n - 2logn - 1 in terms of array element comparisons. Simply build a min heap (rooted at 1). Return the smaller of numbers at index 2 or 3 in the array. The cost of min heap building is = 2 * [n/4 + 2n/8 + ...... + (logn - 1) * n / 2^logn]. The solution to this arithmetic - geometric series is 2n - 2logn - 2. Comparing elements at 2nd and 3rd index adds one to the cost. Its very easy to implement though

Acknowledgments :

http://n1b-algo.blogspot.com/2008/12/finding-second-smallest-element.html