rohith2506

void find(vector<int> a, int low, int high){
  if(high == low+1 && a[low] <= a[high]) return a[high];
  if(high == low+1 && a[low] >= a[high]) return a[low];
  int mid = (low + high)/2;
  if(a[low] < a[mid] && a[mid] > a[high]) return a[mid];
  if(a[mid-1] < a[mid] && a[mid] < a[mid+1]) return find(a,low,mid-1);
  else return find(a,mid+1, high);
}

rohith2506

// but it uses much more memory than normal external memory
void reverse(stk){
  if(!stk.empty()){
    int temp = stk.top();
    stk.pop();
    reverse(stk);
    insert(temp, stk);
  }
}

rohith2506

// Calculate whole sum 
//1.)Traverse the BST and calculate the total sum of all the nodes
//2.) Again start "Inorder Traversing" and replace the first node with the calculated sum in step 1
//3.) Subtract that first node from the sum and move forward to the second node.
//4.) Again keep on replacing and subtracting till you finish the inorder traversal
//Complexity O(n+n)

void sum_modify(t, tsum){
  inorder(t->left, tsum);
  t->data = tsum;

rohith2506

void toposort(vector<int> v, stack<int> stck, vector<bool> visited){
  visited[i] = true;
  for(int j=0; j<v[i].size(); j++){
    if(visited[i] == true)
      toposort(v,stck,visited);
  }
  stck.push(v);
}

void driver(vector<int> v){

rohith2506

// Use Hashing
// map<node*, node* > = new map<node* , node* >
// Author: Rohith
// This is little bit tricky. Why?? i can't simply create all nodes and recrusively call them.
// we can do like this

void copylandr(t){
  node *clone = new node(t->key);
  mp[t] = clone;
  copylandr(t->left, mp);

rohith2506

/*
Maintain two heaps. maxheap and minheap
The difference between elements in both heaps is atmost 1.
if elements in both heaps are equal, then take the average of two root elements of two heaps.
else return the root element of max heap.
if diff of elements is more than 1, then add those root elements in max heap to minheap and adjust maxheap.
voila, you will get your answer.
for heap:- https://github.com/rohspeed/Algo-world/blob/master/dsa_easy/heap_sort.cpp
pseudo code
*/

rohith2506

// For eg: 396 --> i=0 => and j = 2 swap(3,6) ==> 693 ==> sort(1..n) => 6 [93] => 639 (this is the required number)
int ngd(n){
  if number is sorted in ascedning order just swap last two digits
  if number is sorted in descending order impossible
  else {
    find the condition a[j] > a[j-1] from last and stop there
    let n1 = a[j]
    find next smallest greater digit than n1
    let n2 = a[i]
    swap(a[j], a[i])

rohith2506

// Merge two sorted arrays
// http://www.geeksforgeeks.org/merge-one-array-of-size-n-into-another-one-of-size-mn/
// Time complexity: 0(m+n)

void merge(A, B){
  int k=0;
  for(int i=m; i<m+n; i++)A[i] = B[k];
  k=0;
  i=0;j=m;
  while(k < (m+n)){

rohith2506

// Median of two sorted arrays.
// http://www.geeksforgeeks.org/median-of-two-sorted-arrays/
void median(A,B,n){
  int m1 = median(A);
  int m2 = median(B);
    
  if(n == 0) return ;
  if(n == 1) return (A[0] + B[0])/2;
  if(n == 2) return max(A[0], B[0]) + min(A[1], B[1])/2;
  

rohith2506

// THIS IS IMPORTANT. 
// Using this method from leetcode.
// Let's say A[i], B[j]
// if A[i] < B[j] then kth element will be between i to n and 0 to j. so we dont need to check between 0 to i-1 and j+1 to n
// if A[i] > b[j] then kth element will be between 0 to i and j+1 to n. so we dont need to check between i+1 to n and 0 to j
// if A[j] > B[j] && A[j] < B[j+1] return A[j]
// if B[j] > A[j] && B[j] < A[j+1] return B[j]

So, Algorithm goes like this.