Searching in Sorted Circular Array

In this problem we will try to find the position of an element if exists in a circular sorted array.

To solve this problem we will first try to find the index of the minimum element in the array and then search for the item in the left-part & right-part of the index

Lets take an eg. to solve the problem


Assume first element of the array is 17. Then the array will look like this
Let index be 10 (position of the min element) Now if we carefully see the values we will find that values in indices [1, 9] & [10, N] are increasing and min(values[1, 9]) > max(values[10, N])
Observing this we can find index using Binary Search (I will use Binary Search using Bit Manipulation) in O(log N) time

Let j = index + 2i
There are two cases while comparing A[j] & A[index]

1. A[index] < A[j]
   j is in the left-part (i.e [1, 9] in our example). So, index is incremented to j
2. A[index] > A[j]
   j is in the right-part (i.e [10, N]) & position of min element is ≤ j so we don't update index

After this operation index will point to the max element in left-part. Hence, index + 1 gives the position of min element in A. And atlast we search for the item in left-part & right-part using Binary Search

import java.util.Scanner;

class CircularArraySearch {
    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 trough = 0;
        for (int i = Integer.highestOneBit(N); i > 0; i >>= 1) {
            int j = trough | i;
            if (j <= N && A[Math.max(1, trough)] < A[j]) {
                trough = j;
                if (A[trough - 1] > A[trough]) break;
            }
        }
        trough = trough % N + 1;
        int item = in.nextInt();
        int index = find(A, item, trough, N);
        if (index < 0) {
            index = find(A, item, 1, trough - 1);
        }
        if (index > 0) {
            System.out.println("Found at " + index);
        } else {
            System.out.println("Not found");
        }
    }
    
    private static int find(int[] A, int item, int l, int r) {
        int index = 0;
        int N = r - l + 1;
        for (int i = Integer.highestOneBit(N); i > 0; i >>= 1) {
            int j = index | i;
            if (j < N && A[j + l] <= item) {
                index = j;
                if (A[j + l] == item) break;
            }
        }
        index += l;
        return item == A[index] ? index : -index;
    }
}

Input

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

Output

Found at 7

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]