Binary Search using Bit Manipulation

Binary Search using Bit Manipulation is quite similar to the normal binary search that we use.
Let index point to the index in A after i bits from MSB are completed. When all bits are checked index gives the position where search item may exist.
Let j = index + 2i
Now let see the three cases

1. item > A[j]
   hence the position of item (if exists) is greater than j. So, index is updated as index + 2i, i.e. set the i^th bit in index
2. item < A[j]
   the position of item is [index, j). So, index is unchanged for this
3. item == A[j]
   bingo!!

import java.util.Scanner;

class Search {
    public static void main (String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] A = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            A[i] = in.nextInt();
        }
        int item = in.nextInt();
        int index = 0;
        for (int i = Integer.highestOneBit(N); i > 0; i >>= 1) {
            int j = index | i;
            if (j <= N && item >= A[j]) {
                index = j;
                if (A[index] == item) break;
            }
        }
        if (item == A[index]) {
            System.out.println("Found at " + index);
        } else {
            if (index > 0) System.out.println("Floor is " + A[index]);
            if (index < N) System.out.println("Ceil is " + A[index + 1]);
        }
    }
}

Input

15
2 3 5 7 11 13 17 19 23 29 31 37 43 47 53
29

Output

Found at 10

N Queens using Bit manipulation

With Bit manipulation the N Queens problem runs quite faster than the trivial method of solving N Queens where we always have to check whether the queen can be placed in the current cell (defined as place(row, col) say), & this checking is also not made in constant time! But using Bit manipulation we are only traversing through the cells where a queen can be placed!! i.e. we are not only removing the cost for place(row, col) but also we are completely ignoring the cells where a queen cannot be placed.

I ran N Queens for N = 14 and it took less than 1s to run. While trivial method of cost O(N!) took > 15s

import java.util.Arrays;

class NQueens {
    static int N, count;
    static int[] column;
    
    public static void main (String[] args) {
        N = 5;
        column = new int[N];
        nQueens(0, 0, 0, 0);
        System.out.println(count);
    }
    
    private static void nQueens(int row, int ltDiag, int rtDiag, int down) {
        if (row == N) {
            System.out.println(Arrays.toString(column));
            count++;
            return;
        }
        int mask = ltDiag | rtDiag | down;
        while (mask < (1 << N) - 1) {
            int col = ~mask & mask + 1; // gets rightmost 0-bit
            column[row] = Integer.numberOfTrailingZeros(col);
            int lD = (ltDiag | col) >> 1;
            int rD = (rtDiag | col) << 1 & (1 << N) - 1;
            nQueens(row + 1, lD, rD, down | col);
            mask |= col;
        }
    }
}

Output

[0, 2, 4, 1, 3]
[0, 3, 1, 4, 2]
[1, 3, 0, 2, 4]
[1, 4, 2, 0, 3]
[2, 0, 3, 1, 4]
[2, 4, 1, 3, 0]
[3, 0, 2, 4, 1]
[3, 1, 4, 2, 0]
[4, 1, 3, 0, 2]
[4, 2, 0, 3, 1]
10

The column[] contains the solution, where column[i] gives where in the i^th row the Queen will be placed (Zero based indexing)

Numeric Diamond Pattern

Diamond Pattern using Recursion

class DiamondRecursion {
    static void column(int c, int a) {
        System.out.print(a + " ");
        if (a < c) {
            column(c, a+1);
            System.out.print(a + " ");
        }
    }
    static void row(int r, int a) {
        for (int i=0; i<r-a; i++) 
            System.out.print("  ");
        column(a, 1); System.out.println();
        if (a < r) {
            row(r, a+1);
            for (int i=0; i<r-a; i++) 
                System.out.print("  ");
            column(a, 1); System.out.println();
        }
    }
    public static void main(String args[]) {
        row(new java.util.Scanner(System.in).nextInt(), 1);
    }
}

Diamond Pattern using Iteration

class DiamondIteration {
    static void column(int N, int c) {
        for (int i = 0; i < N-c; i++) 
            System.out.print("  ");
        for (int i = 1; i < c; i++)
            System.out.print(i + " ");
        for (int i=c; i>0; i--)
            System.out.print(i + " ");
        System.out.println();
    }
    static void row(int N) {
        for (int i=1; i<N; i++)
            column(N, i);
        for (int i=N; i>0; i--)
            column(N, i);
    }
    public static void main(String args[]) {
        row(new java.util.Scanner(System.in).nextInt());
    }
}

Input

5

Output

        1
      1 2 1 
    1 2 3 2 1 
  1 2 3 4 3 2 1 
1 2 3 4 5 4 3 2 1 
  1 2 3 4 3 2 1 
    1 2 3 2 1 
      1 2 1 
        1 

Ceil and Floor in Integer Array

Ceil

Ceil of a number (say a) in an sorted array, is the number (say b_ceil in the sorted array), such that b_ceil ≥ a & b_ceil - a is minimum. It can also be said that b_ceil is the minimum number greater than or equal to a.

Floor

Similarly, Floor of a number is b_floor such that b_floor ≤ a & a - b_floor is minimum. Or, b_floor is the minimum number less than or equal to a.

Following Java program finds the ceil & floor of a number in the given array in O(log n) time

import java.util.*;
class CeilNfloor
{
 public static void main (String[] args) {
     Random random = new Random();
     int N = 15;
     int[] A = new int[N];
     for (int i=0; i<N; i++)
         A[i] = random.nextInt(100);
     Arrays.sort(A);
     System.out.println(Arrays.toString(A));
     int item = random.nextInt(100);
     System.out.println("Item is "+item);
     System.out.println("Ceil is "+ceil(A, item));
     System.out.println("Floor is "+floor(A, item));
 }
 
 static int ceil(int[] A, int item) {
     int N = A.length;
     if (item > A[N-1])  return -1;
     else                return ceil(A, 0, N-1, item);
 }
 
 static int ceil(int[] A, int low, int high, int item) {
     int mid = (low + high) >> 1;
     if (low > high)     return A[low];
     if (A[mid] == item) return A[mid];
     if (item > A[mid])  return ceil(A, mid+1, high, item);
                         return ceil(A, low, mid-1, item);
     
 }
 
 static int floor(int[] A, int item) {
     if (item < A[0]) return -1;
     return floor(A, 0, A.length-1, item);
 }
 
 static int floor(int[] A, int low, int high, int item) {
     int mid = (low + high) >> 1;
     if (low > high)     return A[high];
     if (item == A[mid]) return A[mid];
     if (item > A[mid])  return floor(A, mid+1, high, item);
                         return floor(A, low, mid-1, item);
 }
}

Output
[8, 18, 20, 24, 55, 65, 65, 66, 67, 68, 70, 74, 83, 95, 96]
Item is 4
Ceil is 8
Floor is -1

Gaussian Elimination

The following C program finds the solution to system of linear equations using Gaussian Elimination, given there exists a unique solution to the problem

#include <stdio.h>
#include <stdlib.h>
int no;
double **A, *B, *x;
void Gauss(int n) {
    int r, c, d=no-n;
 
    if(n != 1) {
        for(r=d+1; r < no; r++) {
            for(c=d+1; c<no; c++)
                A[r][c] -= A[r][d]/A[d][d] * A[d][c];
            B[r] -= A[r][d]/A[d][d] * B[d];
            A[r][d]=0;
        }
        Gauss(n-1);
    }
 
    for(c=d+1; c<no; c++)
        B[d] -= A[d][c]*x[c];
    x[d] = B[d]/A[d][d];
}
void acceptNsolve() {
    int r, c;
    printf("Enter the no of unknowns\n");
    scanf("%d", &no);
    printf("Enter the coefficient matrix\n");
    A=malloc(no);
    for(r=0; r<no; r++) {
        A[r] = malloc(no * sizeof(double));
        for(c=0; c<no; c++)
            scanf("%lf", &A[r][c]);
    }
    printf("Enter value of constants in the column vector\n");
    B = malloc(no * sizeof(double));
    for(r=0; r<no; r++)
        scanf("%lf", &B[r]); 
    x = malloc(no * sizeof(double));
    Gauss(no);
    printf("The solution of the given linear equations is\n");
    for(r=0; r<no; r++)
        printf("%g\n",x[r]);
}
int main() {
    acceptNsolve();
    return 0;
}

Input:
Enter the no of unknowns
3
Enter the coefficient matrix
5 3 1
2 1 3
1 2 4
Enter value of constants in the column vector
16 19 25

Output:
The solution of the given linear equations is
1
2
5

All Subsets

The following Python program generates all ordered subsets of a list. This method is very useful in brute-force approach of solving a problem

def generateSubsets(A, n, sub=[]):
    if n == 0:
        print(sub)
        return
    generateSubsets(A, n-1, sub)
    generateSubsets(A, n-1, [A[n-1]] + sub)

A = list(map(int, input().split()))
generateSubsets(A, len(A))

Input:
1 2 3 4

Output:
[]
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]
[4]
[1, 4]
[2, 4]
[1, 2, 4]
[3, 4]
[1, 3, 4]
[2, 3, 4]
[1, 2, 3, 4]

Sorted List to Complete Binary Tree

The following Python program creates a balanced Binary Tree from a given sorted list Θ(length of sorted list)

class SortedBST:
    class Node:
        def __init__(self, val):
            self.value = val
            self.left = None
            self.right = None
   
    def __init__(self, nos):
        self.nos = nos
        self.root = None
        self.root = self.initBST(self.root, 0, len(nos) - 1)
  
    def initBST(self, node, low, high):
        mid = (low + high) >> 1
        node = self.Node(self.nos[mid])
        if low < mid:
            node.left = self.initBST(node.left, low, mid-1)
        if high > mid:
            node.right = self.initBST(node.right, mid+1, high)
        return node
  
    def BFS(self):
        from collections import deque
        q = deque()
        q.append(self.root)
        while(q):
            qv = q.popleft()
        print(qv.value)
        if qv.left != None:
            q.append(qv.left)
        if qv.right != None:
            q.append(qv.right)
 
sortedList = sorted(list(map(int, input().split())))
sortedBst = SortedBST(sortedList)
sortedBst.BFS()