Add two numbers represented by linked lists using recursive

Add two numbers represented by linked lists using recursive method and generate the 3td linked with addition of 1st and 2nd linked list.

For example:


val_1[] = {       7, 6, 5 }
val_2[] = { 9, 6, 4, 1, 6 }


then the output should be {9, 7, 1, 8, 1} basically its addition of 1st and 2nd linked lists as same normal 2 numbers addition.

Add two numbers represented by linked lists using recursive

         
Let's see simple java code to create linked lists using input array and to get the addition of 2 linked list in 3rd linked list.



public class SumOfTwoLL {
 
 class NODE {

  int data;
  NODE next;

  public NODE(int data) {
   this.data = data;
   this.next = null;
  }
 }

 public static void main(String[] args) {

  SumOfTwoLL obj = new SumOfTwoLL();
  
  int val_1[] = new int[] {       7, 6, 5 };
  int val_2[] = new int[] { 9, 6, 4, 1, 6 };

  // Create linked list out of arrays
  NODE first = obj.createLinkedList(val_1);
  NODE second = obj.createLinkedList(val_2);
  
  // Check no. of nodes in both Linked list
  int t1 = obj.noOfNodes(first);
  int t2 = obj.noOfNodes(second);
  
  // Adjusting Linked List with leading zero node's to make it equal size
  if(t1 < t2) first = obj.adjustLinkedList(first, (t2-t1));
  else if(t2 < t1) second = obj.adjustLinkedList(second, (t1-t2));
  
  // add method call
  NODE third = obj.addTwoLL(first, second, 0);
  
  obj.print(third);
  
 }
 
 // Method to get sum of 2 Linked List
 private NODE addTwoLL(NODE first, NODE second, int cnt) {
  
  if(first != null && second != null){
   
   // Recursive call moving to last node 
   NODE node = addTwoLL(first.next, second.next, cnt+1);
   
   // Calculating sum from last 2 values 
   int val = (first.data + second.data) +node.data;
   
   int carry = val/10;
   int sum = val%10;
   
   // If carry present or not the first node in list then create a node with carry value
   if(cnt != 0 || carry > 0) {
   
    NODE carryNode = new NODE(carry);
    node.data = sum;
    carryNode.next = node;
    return carryNode;
   
   }else {
    // Assign final sum to the previous cycle carry node
    node.data = sum;
    return node;
   }
  }
  // Create last carry node with zero
  return new NODE(0);
 }
 

 private NODE adjustLinkedList(NODE ll, int noOfNodesToAdd){
  while(noOfNodesToAdd > 0){
   NODE tmp = new NODE(0);
   tmp.next = ll;
   ll = tmp;
   noOfNodesToAdd--;
  }
  return ll;
 }
 
 
 private int noOfNodes(NODE ll){
  int count = 0;
  while(ll !=  null){
   count ++;
   ll = ll.next;
  }
  return count;
  
 }
 
 public NODE createLinkedList(int val[]) {
  NODE start = null;
  for (int i : val) {
   NODE tmp = new NODE(i);
   if (start == null) {
    start = tmp;
   } else {
    NODE mover = start;
    while (mover.next != null) {
     mover = mover.next;
    }
    mover.next = tmp;
   }
  }
  return start;
 }
 

 public void print(NODE tmp){
  while(tmp != null ){
   System.out.print(tmp.data +", ");
   tmp = tmp.next;
  }
 }
}



OUTPUT:

9, 7, 1, 8, 1, 



Reverse words in a given String using recursion

Reverse words in a given String using recursion. We need to reverse words by words in a given line and not the character in a given string. We need to solve this by using backtracking and recursion logic.
Reverse words in a given String using recursion

Let's see simple Java code for getting the given of words in a reverse order by using recursion.


public class ReverseLineByWords {

 public static void main(String[] args) {
  
  String str = "Hello Java Discover";
  
  String finalStr = new ReverseLineByWords().reverseLine(str);
  
  System.out.println(finalStr);
  
 }
 
 public String reverseLine(String str){
  String word = "";
  int i = 0;
  for(;i<str.length();i++){
   if(str.charAt(i) == ' ') {
    word = word + " ";
    break;
   }else{
    word = word + str.charAt(i);
   }
  }

  if(i < str.length()) 
   return reverseLine(str.substring(i+1)) + word;
  
  return (word + " ");
 }
}


OUTPUT:


Discover Java Hello 


Rotate matrix by clockwise

Given a NxN matrix and need to rotate by clockwise as given below

Examples:
Rotate matrix by clockwise


Let's see simple java code to rotate given NxN matrix.


public class MatrixRotate {

 private int prev, curr;

 public static void main(String[] args) {

  int[][] matrix = new int[][] { { 1, 2, 3, 4 }, 
                   { 5, 6, 7, 8 }, 
            { 9, 10, 11, 12 }, 
            { 13, 14, 15, 16 } };
  

  MatrixRotate obj = new MatrixRotate();
  obj.rotateMatrix(matrix);

  for (int i = 0; i < matrix.length; i++) {
   System.out.println();
   for (int j = 0; j < matrix[0].length; j++) {
    System.out.print(matrix[i][j] + ", ");
   }
  }
 }

 public void rotateMatrix(int[][] matrix) {

  int r = matrix.length;
  int c = matrix[0].length;
  int row = 0, col = 0;

  for (int cnt = 0;cnt<(r*c);cnt++) {
   
   prev = matrix[row + 1][col];

   for (int i = col; i < c; i++) {
    swap(row, i, matrix); cnt++;   }
   row++;

   for (int i = row; i < r; i++) {
    swap(i, c - 1, matrix); cnt++;   }
   c--;

   if (row < r) {
    for (int i = c - 1; i >= col; i--) {
     swap(r - 1, i, matrix); cnt++;
    }
   }
   r--;

   if (col < c) {
    for (int i = r - 1; i >= row; i--) {
     swap(i, col, matrix); cnt++;
    }
   }
   col++;
  }
 }

 public void swap(int i, int j, int matrix[][]) {
  curr = matrix[i][j];
  matrix[i][j] = prev;
  prev = curr;
 }
}


OUTPUT:


 5,  1,  2,  3, 
 9, 10,  6,  4, 
13, 11,  7,  8, 
14, 15, 16, 12, 



Find the smallest window in a string containing all characters of another string (With smallest window)

Given two strings string1 and string2, find the smallest substring in string1 containing all characters of string2 efficiently.
For Example:
Find the smallest window in a string containing all characters of another string (With smallest window)
Steps:
  • Generate all substrings which starts with any one character from the pattern string
  • Iterate all substrings which we generated and compare each character from the pattern string with the substring and check for all characters present or not
  • If all characters present in substring then trim extra characters and choose the smallest window string

Java code:


public class StringInSmallestWindow {

 public static void main(String[] args) {

  String str = "niharika";
  String findStr = "ir";
  String result = null;

  if (str.length() < findStr.length()) {
   System.out.println("Pattern string is greater than source string");
   return;
  }

  int j = 0;
  String[] arr = new String[str.length()];
  // Get all substring which starts with any one character from the
  // pattern string
  for (int i = 0; i < str.length(); i++) {
   if (findStr.contains(str.charAt(i) + "") && str.substring(i).length() >= findStr.length()) {
    arr[j++] = str.substring(i);
   }
  }

  // Iterate all substrings which we generated
  for (int pnt = 0; pnt < j; pnt++) {

   String string = arr[pnt];
   char[] tmp = findStr.toCharArray();

   int cnt = tmp.length;
   int lastIndex = 0;

   // Compare each character from the pattern string with the substring
   // and check for all characters present or not
   for (int i = 0; i < tmp.length; i++) {

    if (string.contains(tmp[i] + "")) {
     if (lastIndex < string.indexOf(tmp[i])) {
      lastIndex = string.indexOf(tmp[i]);
     }
     string = string.substring(0, string.indexOf(tmp[i])) + '\0'
       + string.substring(string.indexOf(tmp[i]) + 1);
     tmp[i] = '\0';
     cnt--;
    }
   }

   // If all characters present in substring then trim extra characters
   // and choose the smallest window string
   if (cnt <= 0) {
    arr[pnt] = arr[pnt].substring(0, lastIndex + 1);
    result = arr[pnt].length() < result.length() ? arr[pnt] : result;
   }

  }
  System.out.println("\nInput String           : " + str);
  System.out.println("\n2nd String to find     : " + findStr);
  System.out.println("\nSmallest window string : " + result);
 }
}


OUTPUT:


Input String           : niharika

2nd String to find     : ir

Smallest window string : ri

How to find missing number in a sequential array ?

 
Given a list of sequential integers and need to finding a missing number from the list of numbers. For example if we have an array like

Finding missing number


Example:1
array = {1,2,3,5,6}
Finding missing number 4

Example:2
array = {14,15,16,18,19,20}
then the missing number is 17

Using XOR operation and finding the missing number.

  • Iterate all the elements and do XOR with each other. 
  • Iterate all the numbers between given smallest and greatest number. In our above example between 1 to 6 and 14 to 20.
  • Next do XOR with both results which gives the missing number

Lets see simple Java code implementation



public class FindingMissingNumber {

 public static void main(String[] args) {
  
  int[] arr = new int[]{11,12,13,15,16,17,18,19};
  int sr = 11;
  int er = 19;
  
  FindingMissingNumber obj = new FindingMissingNumber();
  
  System.out.println("Missing number using XOR : "+obj.findMissingNumberUsingXOR(arr, sr, er));
 }
 
 public int findMissingNumberUsingXOR(int[] arr, int sr, int er){
  
  int xor = 0;
  int actualXor = 0;
  
  for(int i=0;i<arr.length;i++){
   xor = xor ^ arr[i];;
  }
  
  for(int i=sr;i<=er;i++){
   actualXor = actualXor ^ i;
  }
  
  return (xor ^ actualXor);
 }
}



OUTPUT:



Missing number using XOR : 14




Split the array into two equal Sum subarrays

Given an array of integers greater than zero, find it possible to split it in two subarrays such that the sum of the two subarrays is the same or with minimal difference. Print the two subarrays.
Split the array into two equal Sum subarrays


Examples:

Input: {5,7,9,2,69,23,9,1,8,5,7,3,6,16}

Output
1st Array sum  : 85
2nd Array sum : 85

ARRAY-1 : 69, 8, 7, 1, 
ARRAY-2 : 23, 2, 16, 3, 9, 5, 9, 5, 6, 7, 


Input: {1,2,3,4,5,6,7,8,9,10}

Output:
1st Array sum  : 27
2nd Array sum : 28

ARRAY-1 : 10, 8, 2, 6, 1, 
ARRAY-2 : 9, 3, 7, 4, 5, 


Lets see simple solution how to split the given array with equal sum or minimal difference.

Steps:
1. Sort the given array.
2. Iterate the array from both end and place the values in 2 different arraylist and also maintain the sum of both list.
3. On each iteration check for both sum difference and if they are not equal then swap difference value from 1st array to 2nd array or wise-verse to make it equal or minimal difference between both the array. 
4. Finally print both the array sum and list of elements in both array.

Simple java code for the above solution:


import java.util.ArrayList;
import java.util.List;

public class ArrayPartition {

 public static void main(String[] args) {
  
  int[] array = new int[] {5,7,9,2,69,23,9,1,8,5,7,3,6,16};
  //int[] array = new int[] {1,2,3,4,5,6,7,8,9,10,1,3,3,6};
  //int[] array = new int[] {5,5,2,2,1,1,2};
  //int[] array = new int[] {1,2,3,4,5,6,7,8,9,10};
  //int[] array = new int[] {100,50,55,2,2,1};
  //int[] array = new int[] {1 , 2 , 3 , 6, 12};
  //int[] array = new int[] {1,2,3,4};
  //int[] array = new int[] {1000, 5000, 3000, 1000};
  //int[] array = new int[] {1,2,3,4,5,6,7};
  //int[] array = new int[] {1,1,1,1,1,1,2,4,2,2,1,3};
  //int[] array = new int[] {10,100,50,110};
  //int[] array = new int[] {4, 1, 2, 3};
  //int[] array = new int[] {500000, 1,332234,3565, 332234};
  
  // Sort the given array
  sortArray(array);
  
  // Call partition method to split the array
  partition(array);
  
 }

 public static void partition(int[] array) {

  List<Integer> arr1 = new ArrayList<Integer>();  
  List<Integer> arr2 = new ArrayList<Integer>();  
  
  int sum1 = 0, sum2 = 0;
  
  // Place last value (largest) value in array1
  arr1.add(array[array.length-1]);
  sum1 = array[array.length-1];


  // Iterate remaining values in array
  for (int i=0,j=array.length-2;i<=j;) {
   
   if(sum2 <= sum1) {
    arr2.add(array[i]); 
    sum2 += array[i]; 
    i++;
   }else {
    arr1.add(array[i]); 
    sum1 += array[i]; 
    i++;
   }
 
   if(i <= j) {
    if(sum2 <= sum1) {
     arr2.add(array[j]); 
     sum2 += array[j]; 
     j--;
    }else {
     arr1.add(array[j]); 
     sum1 += array[j]; 
     j--;
    }
   }
   }
   // Reorder array1 and array2 with equal sum or minimal sum
   if(sum1 > sum2) {
    int diff = (sum1 - sum2)/2;
    if(arr1.contains(diff) && diff > 0) {
     int sum[] = replaceArrayElement(arr1, diff, arr2, sum1, sum2);
     sum1 = sum[0];
     sum2 = sum[1];
     
    }
    
    while(sum1 > sum2 && diff > 0) {
     diff--;
     if(arr1.contains(diff) && diff > 0) {
      int sum[] = replaceArrayElement(arr1, diff, arr2, sum1, sum2);
      sum1 = sum[0];
      sum2 = sum[1];
      diff++;
     }
    }
   }
   
   // Reorder array1 and array2 with equal sum or minimal sum
   if(sum2 > sum1) {
    int diff = (sum2 - sum1)/2;
    if(arr2.contains(diff) && diff > 0) {
     int sum[] = replaceArrayElement(arr2, diff, arr1, sum2, sum1);
     sum2 = sum[0];
     sum1 = sum[1];
    }
    
    while(sum2 > sum1 && diff > 0) {
     diff--;
     if(arr2.contains(diff) && diff > 0) {
      int sum[] = replaceArrayElement(arr2, diff, arr1, sum2, sum1);
      sum2 = sum[0];
      sum1 = sum[1];
      diff++;
     }
    }
   }
  
  System.out.println("1st Array sum  : "+sum1);
  System.out.println("2nd Array sum : "+sum2);
  
  System.out.print("\nARRAY-1 : ");
  for (Integer integer : arr1) {
   System.out.print(integer +", ");
  }
  
  
  System.out.print("\nARRAY-2 : ");

  for (Integer integer : arr2) {
   System.out.print(integer +", ");
  }
 }
 
 private static int[] replaceArrayElement(List<Integer> arr1, int diff, List<Integer> arr2, int sum1, int sum2) {
  
  int in = arr1.indexOf(diff);
  arr1.remove(in);
  sum1 = sum1 - diff;
  arr2.add(diff);
  sum2 = sum2 + diff;
  
  return new int[] {sum1, sum2};
 }

 private static void sortArray(int[] array) {

  for(int i=0;i<=array.length-1;i++) {
   for(int j=i+1;j<=array.length-1;j++) {
    if(array[i] > array[j]) {
     int tmp = array[i];
     array[i] = array[j];
     array[j] = tmp;
    }
   }
  }
 }
}

OUTPUT:


1st Array sum  : 85
2nd Array sum : 85

ARRAY-1 : 69, 8, 7, 1, 
ARRAY-2 : 23, 2, 16, 3, 9, 5, 9, 5, 6, 7, 

How to do simple matrix multiplication

Simple matrix multiplication with sample java code.

How to do simple matrix multiplication



public class MatrixMultiplication {

 public static void main(String[] args) {
  
  int a[][] = new int[][] { {2,3}, {1,2}, {5,6} };
  int b[][] = new int[][] { {4,5,6}, {1,2,3} };
  
  if(a[0].length != b.length) {
   System.out.println("Multiplication not possible");
   return;
  }
  
  int c[][] = new int[a.length][b[0].length];
  
  for(int i=0;i<a.length;i++)
   for(int j=0;j<b[0].length;j++)
    for(int k=0;k<a[0].length;k++)
     c[i][j] += a[i][k] * b[k][j];
  
  for(int i=0;i<a.length;i++) {
   for(int j=0;j<b[0].length;j++)
    System.out.print(c[i][j] + " ");
   System.out.println();
  }
 }
}


OUTPUT:


11   16    21 
6    9     12 
26   37   48