Pages
Showing posts with label Core Java. Show all posts
Showing posts with label Core Java. Show all posts

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

How to find the largest subarray with sum 0

 
Given an array of integers, find the largest subarray with sum equals to 0. If theres no subarray with sum 0 then print as "No subarray with sum 0".
How to find the largest subarray with sum 0
As solution we are going to iterate the give array from 0th index to nth index and sum each values and finding the subarray.
Solution:
  • Iterating from starting to end of the array
  • Iterating sub array from 'start' to 'end' pointer and break if sum zero got or sub array smaller than previous sub array with zero 
Lets see simple java code


public class SubArrayZero {

 public static void main(String[] args) {

  int array[] = new int[] { 15, -2, 2, -8, 0, 1, 7, 10, 23 };

  SubArrayZero obj = new SubArrayZero();

  obj.getSubArraySumZero(array);
 }
 
 public void getSubArraySumZero(int[] array) {

  int start = 0, end = 0, sum = 0, fStart = 1, fEnd = -1;

  // Iterating from starting to end of the array
  for (int i = 0; i < array.length; i++) {

   end = i;
   sum += array[i];

   if (sum == 0) {
    if ((fEnd - fStart) < (end - start)) {
     fStart = start;
     fEnd = end;
    }
   } else {
    int tSum = sum;
    
    /* Iterating sub array from 'start' to 'end' pointer and break
    *  if sum zero got or sub array smaller than previous sub array with zero 
    */
    for (int j = start; j < end; j++) {
     tSum -= array[j];
     if (tSum == 0) {
      if ((fEnd - fStart) < (end - (j + 1))) {
       fStart = j + 1;
       fEnd = end;
      }
      break;
     } else if ((fEnd - fStart) > (end - (j + 1)))
      break;
    }
   }
  }
  if(fEnd != -1) {
   System.out.println("Start Index : " + fStart);
   System.out.println("End Index   : " + fEnd);
  }else {
   System.out.println("No subarray with sum 0");
  }
 }
}

OUTPUT:


Start Index : 1
End Index   : 6

How to find integer pairs with given sum

 
Given an array of integers, and a number ‘sum’, find the number of pairs of integer in the array whose sum is equal to ‘sum’.
How to get integer pairs with given sum from integer array

Array can be a combination of +ve, -ve and duplicate elements. Where we need to get the list of all unique pairs from the given array which makes sum is equal to given number. Easy solution with O(N) time complexity will be 
  • Iterate each element from array and store it in Set.
  • Compare the elements difference from sum as whether present in the Set or not. If present then print the pair with element and sum difference. 
  • Remove the difference element from Set to avoid generating duplicate pair. 
Lets see simple Java solution


import java.util.HashSet;

public class PairSum {

 public static void main(String[] args) {

  int[] val = new int[] { 1, 7, 3, 3, 3, 4, 3, -1, 3, 6, 6, 6, 6, 2, 6, 3, 3, 5, 8, 10 };
  PairSum obj = new PairSum();
  obj.getPairs(val, 9);
 }

 public void getPairs(int[] val, int sum) {
  
  HashSet<Integer> set = new HashSet<Integer>();
  int count = 0;
  for (int i : val) {
   if (set.contains(sum - i)) {
    System.out.println("Pair : (" + (sum - i) + ", " + i + ")");
    set.remove(sum - i); // Removing existing value from set to avoid duplicate pair to print
    count++;
   }
   set.add(i);
  }
  
  System.out.println("\nNo. of pairs : "+count);
 }
}

OUTPUT:


Pair : (3, 6)
Pair : (7, 2)
Pair : (6, 3)
Pair : (4, 5)
Pair : (1, 8)
Pair : (-1, 10)

No. of pairs : 6
Get updates in your email box

Complete the form below, and we'll send you our recent update.

Deliver via FeedBurner
© Copyright 2015 Java Discover. Designed by Bloggertheme9 | Distributed By Gooyaabi Templates. Powered by Blogger.