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()

Round A APAC Test 2014

Cut Tiles

Problem

Enzo is doing renovation for his new house. The most difficult part is to buy exactly the right number of tiles. He wants N tiles of different sizes. Of course they have to be cut from the tiles he bought. All the required tiles are square. The lengths of side of the tiles are 2^S₁, 2^S₂, ..., 2^S_N. He can only buy a lot of tiles sized M*M, and he decides to only cut tiles parallel to their sides for convenience. How many tiles does he need to buy?

Input

The first line of the input gives the number of test cases: T. T lines follow. Each line start with the number N and M, indicating the number of required tiles and the size of the big tiles Enzo can buy. N numbers follow: S₁, S₂, ... S_N, showing the sizes of the required tiles.

Output

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the number of the big tiles Enzo need to buy.

The solution for the problem is written in Java

import java.io.File;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class CutTiles {   
    Scanner in;
    int T, N, M;
    Integer[] S;
 
    int solve() {
        byte limit = (byte) Math.floor(Math.log(M)/Math.log(2));
        int tiles = 1, newN = 0;
        double eaten = 0; 
  
        N = in.nextInt();
        M = in.nextInt();
        S = new Integer[N];
        for (int i=0; i<N; i++) {
            S[i] = in.nextInt();
            assert S[i] <= limit;
        }
        Arrays.sort(S, new Comparator<Integer>() {
            public int compare(Integer a, Integer b) {
                return b-a;
            }
        });
  
        for (int i=0; i<N; i++) {
            long powS = (long) Math.pow(2, S[i]);
            long sqs = (M / powS) * (M / powS);
            if (sqs - eaten/powS/powS < 1) {
                if (newN == 0)
                    tiles++;
                S[newN++] = S[i];
            }
            else 
                eaten += powS * powS;
   
            if (i == N-1 && newN > 0) {
                N = newN;
                eaten = newN = 0;
                i = -1;
            }
        }
        return tiles;
    }
    void input() {
        in = new Scanner(System.in);
        T = in.nextInt();
        for (int test=1; test<=T; test++) {
            System.out.print("Case #"+test+": ");
            System.out.println(solve());
        }
    }
 
    public static void main(String[] args) {
        new CutTiles().input();
    }
}

The complexity of the program is O(no. of tiles required * N)