import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

class Main {
  public static void main(String[] args) {

    int A[] = {1,4,45,6,10,8,7,9};
    int n = 16;
    int arr_size = A.length;
    problem1(A, arr_size, n);
    linebreak();
    int a2[] = {1,3,3,1,2,1,2,2,2,1,2,2,2};
    problem2(a2, a2.length);
    linebreak();
    int a3[] = {2,3,4,5,2,4,3,5,2,4,2};
    problem3(a3);
    linebreak();
    int a4[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    System.out.println("Maximum contiguous sum is: " + problem4(a4));
    linebreak();
    int a5[] = {1, 2, 4, 5, 6};
    System.out.println("The missing number is: " + problem5(a5));
    linebreak();
    int a6[] = {1,2,3,4,5,6,7};
    problem6(a6);
    linebreak();
    int a7[] = {1,2,3,4,5,6,7};
    problem7(a7, 3);
    linebreak();
    int a8[] = {3,2,5,10,7};
    problem8(a8);
    linebreak();
    problem9();
    linebreak();
    int a10[] = {18, 17 ,4, 5, 6};
    problem10(a10);
    linebreak();
    int a11[] = {2,4,1,3,5};
    problem11(a11);
    linebreak();
    int a12[] = {12,13,1,10,34,1,2};
    problem12(a12);
    linebreak();
    int a16[] = {1,2,3,4,4,4,4};
    problem16(a16,4);
    linebreak();
    int a17[] = {1000,456,348, 2, 8000, 698};
    problem17(a17);
    linebreak();
    int a18[] = {0,1,1,0,1,0,1,1,1,0,0,1,0,1,0};
    problem18(a18);
    linebreak();
    int a19[] = {1,23,12,9,30,2,50};
    problem19(a19,2);
    linebreak();
    int a20[] = {80,2,6,3,100};
    problem20(a20);
    linebreak();
    int a21[] = {2,3,6,80,104};
    problem21(a21,7);
    linebreak();
    int a22[] = {12,34,45,8,30,9,3};
    problem22(a22);
    linebreak();
    int a23[] = {1,2,3,7,3,2,9,8};
    problem23(a23);
    linebreak();
    int a24[] = {4,3,2,7,9,2,3,5,8,8,7};
    problem24(a24);
    linebreak();
    String s1[] = {"asd","fgh","jkl"};
    System.out.println(Arrays.asList(s1).contains("asb"));
    linebreak();
    System.out.println(IsPerfectSquare(121));
    linebreak();
    getSumofDigits("aa23sdsaadsfsd200sdfsf");
    linebreak();
    int a25[] = {0,1,1,0,1,2,1,2,0,0,0,0,1};
    problem25(a25);
    linebreak();
    int a26[] = {1,2,3,1,3,6,6};
    problem26(a26);
    linebreak();
    int a27[] = {0,1,2,3,4,6,7};
    problem27(a27);
    linebreak();
    int a28[] = {1,2,2,3,3,3,3};
    problem28(a28,3);
    linebreak();
    int a29[] = {1,2,3,4,6,1};
    problem29(a29);
    linebreak();
    int a30[] = {4,5,6,7,8,4,4};
    problem30(a30,3);
    linebreak();
  }

  private static void linebreak() {
    System.out.println("--------------------------------------------------------");
  }

  // Given an Array A[] and a number x, check for a pair in A[] with sum 'x'
  private static void problem1(int arr[], int arr_size, int sum) {
    int i, temp;
    boolean[] binMap = new boolean[100000];

    Arrays.fill(binMap, false);

    for(i = 0; i < arr_size ; i++) {
      temp = sum - arr[i];
      if(temp >= 0 && binMap[temp] == true) {
        System.out.println("Pair with given sum " + sum + " is: " + arr[i] + " and " + temp);
      }
      binMap[arr[i]] = true;
    }
  }

  // Given an Array of size 'n', find an element that appears more than n/2 times
  private static void problem2(int[] a2, int length ) {

    int candidate = findCandidate(a2, length);
    if(isMajority(a2, length, candidate)) System.out.println("The majority candidate is: " + candidate);
    else System.out.println("There's no majority element.");
  }

  private static boolean isMajority(int[] a, int size, int cand) {
    int i, count = 0;
    for (i = 0; i < size; i++) {
      if(a[i] == cand) count++;
    }
    if (count > size/2) return true;
    else return false;
  }

  private static int findCandidate(int a[], int size) {
    int maj_index = 0, count = 1;
    int i;
    for(i=1;i < size; i++){
      if(a[maj_index] == a[i]) count++;
      else count--;
      if(count == 0) {
        maj_index = i;
        count = 1;
      }
    }
    return a[maj_index];
  }

  // Find the number occuring odd number of times
  private static void problem3(int[] ar) {
    int size = ar.length;
    int i, res = 0;
    for (i = 0; i< size; i++) {
      res = res ^ ar[i];
    }
    if (res != 0) System.out.println("The number occuring odd number of times is: " + res);
    else System.out.println("There's no such number. ");
  }

  // Largest sum contiguous sub-array
  private static int problem4(int[] a) {
    int size = a.length;
    int max_so_far = a[0], i;
    int curr_max = a[0];

    for(i = 1; i < size; i++) {
      curr_max = max(a[i], curr_max+a[i]);
      max_so_far = max(max_so_far, curr_max);
    }
    return max_so_far;
  }
  private static int max(int x, int y) {
    return (y > x)? y : x;
  }

  // Find the missing number
  private static int problem5(int[] a) {
    int n = a.length;
    int i, total;
    total = (n+1)*(n+2)/2;
    for (i = 0; i < n; i++) total -= a[i];

    return total;
  }

  // Reverse an array
  private static void problem6(int[] ar) {
     System.out.print("Array before reversal: ");
     printArray(ar);

     int n = ar.length;
     int i = 0;
     int j = n-1;

     for(i = 0; i < n/2; i++,j--) {
       int temp = ar[i];
       ar[i] = ar[j];
       ar[j] = temp;
     }
     System.out.print("Array after reversal: ");
     printArray(ar);
  }

  private static void printArray(int[] a) {
    for (int i = 0; i < a.length; i++) System.out.print(a[i] + " ");
    System.out.println("");
  }

  // Rotate an array by given places
  private static void problem7(int[] a, int n) {
     System.out.print("Original Array: ");
     printArray(a);

     int newarr[] = new int[a.length];
     int k = 0;

     for(int i = 0; i < n; i++) newarr[i] = a[i];
     for(int j = n; j < a.length; j++,k++) a[k] = a[j];
     for(int i = n+1, ii = 0; i < a.length; i++, ii++) a[i] = newarr[ii];

     System.out.print("Array after rotation: ");
     printArray(a);
  }

  // Function to return max sum such that no two elements are adjacent
  private static void problem8(int[] a) {
    int n = a.length;
    int incl = a[0];
    int excl = 0;
    int excl_new, i;

    for(i = 1; i < n ; i++) {
      excl_new = (incl > excl) ? incl :  excl;

      incl = excl + a[i];
      excl = excl_new;
    }
    int result = (incl > excl) ? incl : excl;
    System.out.println("The max sum is: " + result);
  }

  // Find union and intersection of 2 arrays
  private static void problem9() {
    int ar1[] = {1,2,3,4,5};
    int ar2[] = {2,4,6};

    HashMap<Integer, Integer> union = new HashMap<Integer, Integer>();
    HashMap<Integer, Integer> intersection = new HashMap<Integer, Integer>();

    for(int i = 0; i < ar1.length; i++) {
      if (!union.containsKey(ar1[i])) union.put(ar1[i], 1);
    }

    for(int i = 0; i < ar2.length; i++) {
      if (!union.containsKey(ar2[i])) union.put(ar1[i], 1);
      else intersection.put(ar2[i],1);
    }

    System.out.print("The union of 2 arrays is: ");
    for(Integer a: union.keySet()) System.out.print(a.toString() + " ");
    System.out.println("");
    System.out.print("The intersection of 2 arrays is: ");
    for(Integer a: intersection.keySet()) System.out.print(a.toString() + " ");
    System.out.println("");
  }

  // Print leaders in an array
  private static void problem10(int[] a) {
    System.out.print("Leaders in the array: ");
    int max_from_right = a[a.length - 1], i;

    System.out.print(max_from_right + " ");
    for(i = a.length - 2; i >= 0; i--) {
      if (max_from_right < a[i]) {
        System.out.print(a[i] + " ");
        max_from_right = a[i];
      }
    }
    System.out.println("");
  }

  // Count inversions in an array
  private static void problem11(int[] a) {

    int n = a.length;
    int inv = 0;
    for(int i = 0; i < n-1 ; i++) {
      for(int j = i+1; j < n ; j++) {
        if(a[i] > a[j]) {
          inv++;
          System.out.println("Inversion# " + inv + " is " + a[i] + " , " + a[j] + ".");
        }
      }
    }
  }

  // Find the smallest and second smallest element in the array
  private static void problem12(int[] a) {
    int n = a.length - 1;
    int one = a[0];
    int two = a[1];

    for(int i = 2; i<=n; i++) {
      if(a[i] < one) {
        two = one;
        one = a[i];
      }
      else if(a[i] < two && a[i] != one) two = a[i];
    }
    System.out.println("The two smallest numbers are: " + one + " and " + two);
  }

  // Check for majority element in an array
  private static void problem16(int[] a, int num) {
    int n = a.length - 1, i = 0, count = 0;
    while(a[i] != num) i++;
    for(int j = i; j <=n; j++) {
      if (a[j] == num) count++;
    }
    if (count > n/2) System.out.println("The majority element is: " + num);
    else System.out.println("There is no majority element.");
  }

  // Find max and min of an array using minimum comparisons
  private static void problem17(int[] a) {
    int n = a.length;
    int min = 0, max = 0;
    if (n == 1) {
      System.out.println("The min and max elements are: " + a[0] + " and " + a[0]);
      return;
  }
  if (a[0] > a[1]) {
    max = a[0];
    min = a[1];
  }
  else {
    max = a[1];
    min = a[0];
  }

  for(int i = 2; i<n ; i++) {
    if (a[i] > max) max = a[i];
    else if (a[i] < min) min = a[i];
  }
  System.out.println("The min and max elements are: " + min + " and " + max);
  return;
}

  // Seggregate 0s and 1s in an array
  private static void problem18(int[] a) {
    printArray(a);
    int n = a.length;
    int count0 = 0, count1 = 0;
    for(int i = 0; i < n; i++) {
      if(a[i] == 0) count0++;
      else count1++;
    }
    System.out.println("The counts of 0 and 1 are: " + count0 + " and " + count1);
    int index;
    for(index = 0; index <= count0; index++) a[index] = 0;
    for(index = count0; index < n; index++) a[index] = 1;
    printArray(a);
  }

  // k smallest and largest elements in an array
  private static void problem19(int[] a, int k) {
    printArray(a);
    mergeSort(a, 0, a.length-1);
    printArray(a);

    System.out.print("The " + k + " smallest elements are: ");
    for(int i = 0;i < k; i++) System.out.print(a[i] + " ");
    System.out.println("");
    System.out.print("The " + k + " largest elements are: ");
    for(int i = a.length - k;i < a.length; i++) System.out.print(a[i] + " ");

    System.out.println("");
  }

  private static void mergeSort(int[]a, int l, int r) {
    if (l < r) {
      int m = (l + r)/2;
      mergeSort(a,l,m);
      mergeSort(a,m+1,r);
      merge(a,l,m,r);
    }
  }

  private static void merge(int[]a, int l, int m, int r) {
    int i,j,k;
    int n1 = m-l+1;
    int n2 = r-m;

    // create temp arrays
    int L[] = new int[n1];
    int R[] = new int[n2];

    // copy data to temp arrays.
    for(i=0;i<n1;i++) L[i] = a[l+i];
    for(j=0;j<n2;j++) R[j] = a[m+1+j];

    // merge temp arrays back to a.
    i = 0;j = 0;k = l;

    while(i < n1 && j < n2) {
      if(L[i] <= R[j]) {
        a[k] = L[i];
        i++;
      }
      else {
        a[k] = R[j];
        j++;
      }
      k++;
    }

    // copy remaining elements of L[]
    while(i < n1) {
      a[k] = L[i];
      i++;
      k++;
    }
    // copy remaining elements of R[]
    while(j < n2) {
      a[k] = R[j];
      j++;
      k++;
    }
  }

  // Max difference between two elements such that larger appears after smaller
  private static void problem20(int[] a) {
    int n = a.length;
    int diff = a[1] - a[0];
    int curr_sum = diff;
    int max_sum = curr_sum;

    for(int i = 1;i < n-1; i++) {
      diff = a[i+1] - a[i];
      if(curr_sum > 0) curr_sum += diff;
      else curr_sum = diff;

      if(curr_sum > max_sum) max_sum = curr_sum;
    }
    System.out.println("The maximum difference is: " + max_sum);
  }

  // Floor and Ceiling in a sorted array for the given number
  private static void problem21(int[] arr, int num) {
    if(arr[0] > num) {
      System.out.println("Floor is missing. The Ceiling is: " + arr[0]);
      return;
    }
    if(arr[arr.length - 1] < num) {
      System.out.println("Ceiling is missing. The Floor is: " + arr[arr.length - 1]);
      return;
    }
    int index = 0;
    while(arr[index] < num) index++;
    System.out.println("The number " + num + " has a floor of " + arr[index-1] + " and a ceiling of " + arr[index]);
  }

  // Seggregate odd and even numbers
  private static void problem22(int[] a) {
    printArray(a);
    HashMap<Integer, Integer> odds = new HashMap<Integer, Integer>();
    HashMap<Integer, Integer> evens = new HashMap<Integer, Integer>();

    for(int i = 0; i <= a.length-1; i++)
    if(a[i]%2 == 0) evens.put(a[i],1);
    else odds.put(a[i],1);

    int index = 0;
    for(Integer aa: odds.keySet()) a[index++] = aa;
    for(Integer aa: evens.keySet()) a[index++] = aa;
    printArray(a);
  }

  // Find out two repeating elements in a given array
  private static void problem23(int[] a) {
    int size = a.length;
    HashMap<Integer, Integer> counts = new HashMap<Integer, Integer>();

    for(int i = 0; i < a.length; i++) {
      if(!counts.containsKey(a[i])) counts.put(a[i],1);
      else counts.put(a[i], counts.get(a[i]) + 1);
    }
      System.out.print("The repeating elements are: ");
      for(Integer aa: counts.keySet()) {
        if (counts.get(aa) == 2) {
          System.out.print(aa + " ");
        }
      }
    System.out.println("");
  }

  // Find missing numbers in an array
    private static void problem24(int[] nums) {
      printArray(nums);
        ArrayList<Integer> ret = new ArrayList<Integer>();
        for(int i = 0; i < nums.length; i++) {
            int val = Math.abs(nums[i]) - 1;
            if(nums[val] > 0) {
                nums[val] = -nums[val];
            }
        }
      printArray(nums);
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] > 0) {
                ret.add(i+1);
            }
        }
        System.out.println("The missing numbers are: " + ret.toString());
    }
    // Determine if a number is a perfect square.
    private static boolean IsPerfectSquare(int n) {
	  for(int i=1; i*i<=n; i++)
	  {
		  if(i*i == n) return true;
	  }
	  return false;
    }

    // Find Sum of Number in the String
    private static void getSumofDigits(String ss){

    int i = 0;
		int j = 0 ;
		int len = ss.length() ;
		int currentNum = 0;
		int sum = 0 ;

		while(i<len){
			if(Character.isDigit(ss.charAt(i))) {
				j=i;
				currentNum = 0;
				while(j < len && Character.isDigit(ss.charAt(j))){
					currentNum = currentNum *10 + ss.charAt(j) - 48;
					j++;
					i++;
				}
				sum = sum + currentNum ;
			}
			i++;
		}
  System.out.println(sum) ;
  }

  // Separate 0s, 1s and 2s
  private static void problem25(int[] arr) {
    printArray(arr);
    int n = arr.length;
    int count0 = 0, count1 = 0;
    for(int i = 0; i < n; i++) {
      if(arr[i] == 0) count0++;
      else if(arr[i] == 1) count1++;
    }
    for(int i = 0;i < count0;i++) arr[i] = 0;
    for(int j = count0;j < count0+count1;j++) arr[j] = 1;
    for(int k = count0+count1; k < n; k++) arr[k] = 2;
    printArray(arr);
  }

  // Find duplicates in O(n) time.
  private static void problem26(int[] arr) {
    printArray(arr);
    HashMap<Integer,Integer> visited = new HashMap<Integer,Integer>();

    for(int i=0;i<arr.length;i++) {
      if(!visited.containsKey(arr[i])) visited.put(arr[i], 1);
      else {
        visited.put(arr[i], visited.get(arr[i] + 1));
        System.out.print(arr[i] + " ");
      }
    }
    System.out.println("");
  }

  // Find smallest missing element in a sorted array
  private static void problem27(int[] arr) {
    printArray(arr);
    if(arr[0] != 0) {
      System.out.println("The missing number is 0.");
      return;
    }
    for(int i=1;i<arr.length;i++) {
      if(arr[i] != i) {
        System.out.println("The missing number is: " + i);
        return;
        }
      else continue;
      }
    }

  // Get first and last occurance of a number
  private static int first(int[] arr, int low, int high, int x, int n) {
    if(high >= low) {
      int mid = (high+low)/2;
      if(mid==0 || x>arr[mid-1] && arr[mid] == x) return mid;
      else if(x> arr[mid]) return first(arr, mid+1, high, x,n);
      else return first(arr, low, mid-1,x,n);
    }
    return -1;
  }

  private static int last(int[] arr, int low, int high, int x, int n) {
    if(high>=low) {
      int mid = (high+low)/2;
      if(mid==n-1 || x<arr[mid+1] && arr[mid] == x) return mid;
      else if(x<arr[mid]) return last(arr, low, mid-1,x,n);
      else return last(arr, mid+1, high, x,n);
    }
    return -1;
  }

  private static void problem28(int[] arr, int num) {
  int i, j;
  int n = arr.length;
  i = first(arr,0, n-1,num, n);

  if(i== -1) {
    System.out.println("The number " + num + "does not exist in the array.");
    return;
  }
  j = last(arr,i, n-1,num,n);
  System.out.println(num + " exists " + (j-i+1) + " times.");
  }

  // Given an array find max j-i such that arr[j] > arr[i]
  private static void problem29(int[] arr) {
    printArray(arr);
    int max = -1;
    int n = arr.length;
    for(int i = 0;i<n;i++) {
      for(int j=i+1;j<n;j++) {
        if(arr[j] > arr[i]) {
          if(arr[j] - arr[i] > max) max = arr[j] - arr[i];
        }
      }
    }
    System.out.println("The max j-i difference is: " + max);
  }

  // Given an array of size n and a number k, find all elements that appear more than n/k times
  private static void problem30(int[] arr, int k) {
    int n = arr.length;
    HashMap<Integer,Integer> freq = new HashMap<Integer,Integer>();
    for(int i = 0;i<n;i++) {
      if(freq.containsKey(arr[i])) freq.put(arr[i], freq.get(arr[i])+1);
      else freq.put(arr[i],1);

      Set set = freq.entrySet();
      Iterator it = set.iterator();
      while(it.hasNext()) {
        Map.Entry me = (Map.Entry) it.next();
        if((Integer) me.getValue() > (n/k)) {
          System.out.println(me.getKey() + " has a count of " + me.getValue());
        }
      }
    }
  }

}