Gold Mine Problem :

Rectangular grid of gold mine is given with R rows and C columns. Grid has R x C cells in it.
Each Cell is denoted by an integer , which is the count of gold content in that cell.

Sub rectangle is defined by four integers x1,y1,x2,y2 ,
where 1<=x1<=x2<=R and 1<=y1<=y2<=C.

Aim is to find the total gold in that given sub rectangle.

For Example:

Input Matrix is      
                             2 3 4 5
                             1 7 3 1
                             8 9 4 6
                             7 3 5 6

and  x1=1 , y1=1 , x2= 2 , y2 = 4  (yellow shaded region is the sub rectangle formed by these points).

Then , output should be sum of 2+3+4+5+1+7+3+1 = 26.

Algorithm:-

1. Input : array and two co-ordinates of rectangle say x1,y1 and x2,y2.
2. for i from x1-1 to x2-1 do
3. for j from y1-1 to y2-1 do
4. sum = sum+array[i][j]


Complexity:- O(n2)


Java implementation of algorithm

package problem.goldmine;

import java.util.Scanner;

public class GoldMine {

    public static void main(String[] args) {
       
        System.out.println("Enter row (M): ");  //Input rows
        Scanner scan = new Scanner(System.in);
        int row = Integer.parseInt(scan.nextLine());
       
        System.out.println("Enter column (N): ");  //Input columns
        Scanner scan1 = new Scanner(System.in);
        int column = Integer.parseInt(scan1.nextLine());
       
        int array[][] = new int[row][column];
       
        for(int r=0;r<row;r++){                       // Input binary matrix
            System.out.println("Enter row "+(r+1));
            for(int c=0;c<column;c++){
                Scanner scan2 = new Scanner(System.in);
                array[r][c]=Integer.parseInt(scan2.nextLine());
            }
        }
       
        System.out.println("Enter x1 : "); 
        Scanner scanx1 = new Scanner(System.in);
        int x1 = Integer.parseInt(scanx1.nextLine());
       
        System.out.println("Enter y1 : "); 
        Scanner scany1 = new Scanner(System.in);
        int y1 = Integer.parseInt(scany1.nextLine());
       
        System.out.println("Enter x2 : "); 
        Scanner scanx2 = new Scanner(System.in);
        int x2 = Integer.parseInt(scanx2.nextLine());
       
        System.out.println("Enter y2 : "); 
        Scanner scany2 = new Scanner(System.in);
        int y2 = Integer.parseInt(scany2.nextLine());
       
        System.out.println();
        display(array,row,column);
        System.out.println();
       
        int sum = 0;
        long startTime = System.currentTimeMillis();
        for(int i=x1-1;i<x2;i++){
            for(int j=y1-1;j<y2;j++){
                sum = sum + array[i][j];
            }
        }
        System.out.println("sum of gold mine in rectangle  formed by ("+x1+","+y1+") and ("+x2+","+y2+") ="+sum);
       
        long stopTime = System.currentTimeMillis();
        long elapsedTime = stopTime - startTime;
        System.out.println("Time Taken= "+(double)elapsedTime/1000+" sec");
       
       

    }
   
    static void display(int[][] array,int row,int column) {         //function to display matrix
        for(int r=0;r<row;r++){
            System.out.println();
            for(int c=0;c<column;c++){
                System.out.print(array[r][c]);
            }
        }
       
    }

}


Output:-

Enter row (M):
4
Enter column (N):
4
Enter row 1
2
8
9
7
Enter row 2
5
8
1
7
Enter row 3
5
7
3
5
Enter row 4
4
8
7
4
Enter x1 :
1
Enter y1 :
4
Enter x2 :
2
Enter y2 :
4


2897
5817
5735
4874
sum of gold mine in rectangle  formed by (1,4) and (2,4) =14
Time Taken= 0.0 sec

Matrix Game : Flip The World

Composition and Dimension of Matrix

There is an binary matrix of dimension M x N.
Binary Matrix : Matrix with entries from the Boolean domain B = {0, 1}

Make a move

1. Select any two integer , say x and y such that 1<=x<=M and 1<=y<=N .
2. All the elements in the rectangle or square formed by (1,1) and (x,y) are to be toggled ,i.e. 0 is made 1 and
    1 is made 0.
                                 (1,1) . . . . . . . . . . . . . .
                                    .                .
                                    .                .
                                    .                .
                                    .............(x,y)

 Note : (1,1) is always taken as one of the two co-ordinates.

For Example : Given a  matrix 4 x 4 (M=4, N=4)

                          1 0 1 0
                          1 1 0 0
                          1 0 0 1
                          1 1 1 0

If we choose x=2 and y=3, then new matrix after toggle will be :

                          0 1 0 0
                          0 0 1 0
                          1 0 0 1
                          1 1 1 0


Aim of the Game

Sole aim of the game is to change all elements of the matrix to 1.
This requires some number of moves to be made in order to get the all-ones matrix out of binary matrix.

Calculating number of steps required

Algorithm:-

1.  Input : row , column and array element .
2.  for i from row-1 to 0 do
3.  for j from column-1 to 0 do
4.  if  array[row][column]==0 then
5.  Toggle the matrix
6.  increment the counter
7. Output : all-ones matrix  and number of moves


Complexity : O(n2)


Java Implementation of the algorithm



import java.util.Scanner;

public class FlipTheWorld {


    public static void main(String[] args) {
       
        System.out.println("Enter row (M): ");  //Input rows
        Scanner scan = new Scanner(System.in);
        int row = Integer.parseInt(scan.nextLine());
       
        System.out.println("Enter column (N): ");  //Input columns
        Scanner scan1 = new Scanner(System.in);
        int column = Integer.parseInt(scan1.nextLine());
       
        int array[][] = new int[row][column];
        int count = 0;
        for(int r=0;r<row;r++){                       // Input binary matrix
            System.out.println("Enter row "+(r+1));
            for(int c=0;c<column;c++){
                Scanner scan2 = new Scanner(System.in);
                array[r][c]=Integer.parseInt(scan2.nextLine());
            }
        }
        System.out.println("Original : ");
        display(array,row,column);
        for(int r=row-1;r>=0;r--){                                
            for(int c=column-1;c>=0;c--){
                if(array[r][c]==0){
                    toggle(array,r,c);
                    count = count+1;
                    System.out.println();
                    System.out.println("Matrix after toggle "+count);
                    display(array,row,column);
                }
                   
            }
        }
        int sum = 0;                                        
        for(int i=0;i<row;i++){                            //Checking if resultant matrix is all-ones or not
            for(int j=0;j<column;j++){                     //for this to check , compare the sum of elements
                                                           // of resultant matrix with the product of row and column.
        sum = sum + array[i][j];
            }
        }
        if(sum==row*column){
        System.out.println();
        System.out.println();
        System.out.println("Final : ");
        display(array,row,column);
        System.out.println();
        System.out.println("Number of steps : "+count);
            }
        else{
            System.out.println("Failure of algo");
        }

    }
   
    static void display(int[][] array,int row,int column) {         //function to display matrix
        for(int r=0;r<row;r++){
            System.out.println();
            for(int c=0;c<column;c++){
                System.out.print(array[r][c]);
            }
        }
       
    }

    static void toggle(int array[][],int row,int column){          //function to toggle the matrix
        for(int r=0;r<=row;r++){
            for(int c=0;c<=column;c++){
                if(array[r][c]==1)
                    array[r][c]=0;
                else
                    array[r][c]=1;
            }
        }
    }

}









Output :

Original :

1010
1100
1001
1110
Matrix after toggle 1

0101
0011
0110
0001

Matrix after toggle 2

1011
1101
1000
1111

Matrix after toggle 3

0100
0010
0111
1111

Matrix after toggle 4

1100
1010
1111
1111

Matrix after toggle 5

0011
0101
1111
1111

Matrix after toggle 6

1101
1011
1111
1111

Matrix after toggle 7

0001
0111
1111
1111

Matrix after toggle 8

1001
1111
1111
1111

Matrix after toggle 9

0111
1111
1111
1111

Matrix after toggle 10

1111
1111
1111
1111

Final :

1111
1111
1111
1111

Number of steps : 10
Time Taken= 0.011 sec

Palindrome Count  : All possible substring palindromes inside a string

A string is said to be palindrome, if the reverse of the string is same as itself.
A sub string is any continuous sequence of characters in the string.

Given a string S, finding all non empty sub strings that are palindromes.

For Example:

For Input string , S =abcba

Output should be all possible substring palindromes :

Palindrome 1 : a
Palindrome 2 : abcba
Palindrome 3 : b
Palindrome 4: bcb
Palindrome 5 : c
Palindrome 6 : b
Palindrome 7 : a



Algorithm:

1.  Input : a string str.
2.  for i from 0 to str.length-1  do
3.  for j from i+1 to str.length  do
4.  result = str.substring(i,j)
5. check if result is palindrome  then
6. increment counter


Complexity:  O(n3)


Java implementation of the algorithm:


import java.util.Scanner;

public class PalindromeCount {


    public static void main(String[] args) {
   
        System.out.println("Enter the string : ");
        Scanner scan = new Scanner(System.in);
        String str = scan.nextLine();
        long startTime = System.currentTimeMillis();   
        int count = substr(str);
        System.out.println("Number of palindromes = "+count);
            long stopTime = System.currentTimeMillis();
            long elapsedTime = stopTime - startTime;
            System.out.println("Time Taken= "+(double)elapsedTime/1000+" sec");
    }
   
   

    private static int substr(String str) {
        int len = str.length();
        int count = 0;
        String result = "";
        for(int i = 0;i<len;i++){
            for(int j = i+1;j<=len;j++){
            result = str.substring(i,j);
            if(isPalindrome(result)){
                count = count + 1;
                System.out.println("Palindrome("+i+","+j+") "+(count)+" : "+result);
               
            }
            }
        }
        return count;
    }



    static boolean isPalindrome(String str){
        int len = str.length();
        boolean flag = false;
        String reverse = "";
        for(int i=len-1;i>=0;i--){
            reverse = reverse+str.charAt(i);
        }
        if(str.equals(reverse))
        flag = true;
        return flag;
    }
}


Output:

Enter the string : abcba
Palindrome(0,1) 1 : a
Palindrome(0,5) 2 : abcba
Palindrome(1,2) 3 : b
Palindrome(1,4) 4 : bcb
Palindrome(2,3) 5 : c
Palindrome(3,4) 6 : b
Palindrome(4,5) 7 : a
Number of palindromes = 7
Time Taken= 0.002 sec