WAP to search an element in a sorted and pivoted array

An element in a sorted array can be found in O(log n) time via binary search. But suppose I rotate the sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Now devise a way to find an element in the rotated array in O(log n) time.


/*Program to search an element in a sorted and pivoted array*/
#include

int findPivot(int[], int, int);
int binarySearch(int[], int, int, int);

/* Searches an element no in a pivoted sorted array arrp[]
of size arr_size */
int pivotedBinarySearch(int arr[], int arr_size, int no)
{
int pivot = findPivot(arr, 0, arr_size-1);
if(arr[pivot] == no)
return pivot;
if(arr[0] <= no)
return binarySearch(arr, 0, pivot-1, no);
else
return binarySearch(arr, pivot+1, arr_size-1, no);
}

/* Function to get pivot. For array 3, 4, 5, 6, 1, 2
it will return 3 */
int findPivot(int arr[], int low, int high)
{
int mid = (low + high)/2; /*low + (high - low)/2;*/
printf("%d \t %d \n", mid,arr[mid]);

if(arr[mid] > arr[mid + 1])
return mid;
if(arr[low] > arr[mid])
return findPivot(arr, low, mid-1);
else
return findPivot(arr, mid + 1, high);
}

/* Standard Binary Search function*/
int binarySearch(int arr[], int low, int high, int no)
{
if(high >= low)
{
int mid = (low + high)/2; /*low + (high - low)/2;*/

if(no == arr[mid])
return mid;
if(no > arr[mid])
return binarySearch(arr, (mid + 1), high, no);
else
return binarySearch(arr, low, (mid -1), no);
}
/*Return -1 if element is not found*/
return -1;
}

/* Driver program to check above functions */
int main()
{
int arr[10] = {3, 4, 5, 6, 7, 1, 2};
int n = 5;
printf("Index of the element is %d", pivotedBinarySearch(arr, 7, 5));
getchar();
return 0;
}

WAP to search an element in a sorted and pivoted array

/*Program to search an element in a sorted and pivoted array*/
#include

int findPivot(int[], int, int);
int binarySearch(int[], int, int, int);

/* Searches an element no in a pivoted sorted array arrp[]
of size arr_size */
int pivotedBinarySearch(int arr[], int arr_size, int no)
{
int pivot = findPivot(arr, 0, arr_size-1);
if(arr[pivot] == no)
return pivot;
if(arr[0] <= no)
return binarySearch(arr, 0, pivot-1, no);
else
return binarySearch(arr, pivot+1, arr_size-1, no);
}

/* Function to get pivot. For array 3, 4, 5, 6, 1, 2
it will return 3 */
int findPivot(int arr[], int low, int high)
{
int mid = (low + high)/2; /*low + (high - low)/2;*/
printf("%d \t %d \n", mid,arr[mid]);

if(arr[mid] > arr[mid + 1])
return mid;
if(arr[low] > arr[mid])
return findPivot(arr, low, mid-1);
else
return findPivot(arr, mid + 1, high);
}

/* Standard Binary Search function*/
int binarySearch(int arr[], int low, int high, int no)
{
if(high >= low)
{
int mid = (low + high)/2; /*low + (high - low)/2;*/

if(no == arr[mid])
return mid;
if(no > arr[mid])
return binarySearch(arr, (mid + 1), high, no);
else
return binarySearch(arr, low, (mid -1), no);
}
/*Return -1 if element is not found*/
return -1;
}

/* Driver program to check above functions */
int main()
{
int arr[10] = {3, 4, 5, 6, 7, 1, 2};
int n = 5;
printf("Index of the element is %d", pivotedBinarySearch(arr, 7, 5));
getchar();
return 0;
}

WAP to Find Inorder Successor of Given Node in Binary Search Tree With & Without Parent Pointer

Data Structure used: Binary Search Tree

Algorithm:
1) If right subtree of node is not NULL, then succ lies in right subtree. Do following.
Go to right subtree and return the node with minimum key value in right subtree.
2) If right sbtree of node is NULL, then succ is one of the ancestors. Do following.
Travel up using the parent pointer until you see a node which is left child of it’s parent. The parent of such a node is the succ.

#include
#include

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
struct node* parent;
};

struct node * minValue(struct node* node);

struct node * inOrderSuccessor(struct node *root, struct node *n)
{
// step 1 of the above algorithm
if( n->right != NULL )
return minValue(n->right);

// step 2 of the above algorithm
struct node *p = n->parent;
while(p != NULL && n == p->right)
{
n = p;
p = p->parent;
}
return p;
}

/* Given a non-empty binary search tree, return the minimum data
value found in that tree. Note that the entire tree does not need
to be searched. */
struct node * minValue(struct node* node) {
struct node* current = node;

/* loop down to find the leftmost leaf */
while (current->left != NULL) {
current = current->left;
}
return current;
}

/* Helper function that allocates a new node with the given data and
NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
node->parent = NULL;

return(node);
}

/* Give a binary search tree and a number, inserts a new node with
the given number in the correct place in the tree. Returns the new
root pointer which the caller should then use (the standard trick to
avoid using reference parameters). */
struct node* insert(struct node* node, int data)
{
/* 1. If the tree is empty, return a new,
single node */
if (node == NULL)
return(newNode(data));
else
{
struct node *temp;

/* 2. Otherwise, recur down the tree */
if (data <= node->data)
{
temp = insert(node->left, data);
node->left = temp;
temp->parent= node;
}
else
{
temp = insert(node->right, data);
node->right = temp;
temp->parent = node;
}

/* return the (unchanged) node pointer */
return node;
}
}

/* Driver program to test above functions*/
int main()
{
struct node* root = NULL, *temp, *succ, *min;

//creating the tree given in the above diagram
root = insert(root, 20);
root = insert(root, 8);
root = insert(root, 22);
root = insert(root, 4);
root = insert(root, 12);
root = insert(root, 10);
root = insert(root, 14);
temp = root->left->right->right;

succ = inOrderSuccessor(root, temp);
if(succ != NULL)
printf("\n Inorder Successor of %d is %d ", temp->data, succ->data);
getchar();
return 0;
}

Time Complexity O(nlogn)
Space Complexity O(1)
Run Here https://ideone.com/Bwwe6

2nd Method Without Using Parent Pointer

#include
#include

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;

};

/* Given a non-empty binary search tree, return the minimum data
value found in that tree. Note that the entire tree does not need
to be searched. */
struct node * minValue(struct node* node) {
struct node* current = node;

/* loop down to find the leftmost leaf */
while (current->left != NULL) {
current = current->left;
}
return current;
}


struct node * inOrderSuccessor(struct node *root, struct node *n)
{
if( n->right != NULL )
return minValue(n->right);
struct node *succ=NULL;
while(root)
{
if(n->data < root->data)
{
succ=root;
root=root->left;
}
else if(n->data > root->data)
root=root->right;
else
break;
}
return succ;
}


/* Helper function that allocates a new node with the given data and
NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;


return(node);
}

/* Give a binary search tree and a number, inserts a new node with
the given number in the correct place in the tree. Returns the new
root pointer which the caller should then use (the standard trick to
avoid using reference parameters). */
struct node* insert(struct node* node, int data)
{
/* 1. If the tree is empty, return a new,
single node */
if (node == NULL)
return(newNode(data));
else
{
/* 2. Otherwise, recur down the tree */
if (data <= node->data)
node->left = insert(node->left, data);
else
node->right = insert(node->right, data);

/* return the (unchanged) node pointer */
return node;
}
}

/* Driver program to test above functions*/
int main()
{
struct node* root = NULL, *temp, *succ, *min;

//creating the tree given in the above diagram
root = insert(root, 20);
root = insert(root, 8);
root = insert(root, 22);
root = insert(root, 4);
root = insert(root, 12);
root = insert(root, 10);
root = insert(root, 14);
temp = root->left->right->right;

succ = inOrderSuccessor(root, temp);
if(succ != NULL)
printf("\n Inorder Successor of %d is %d ", temp->data, succ->data);
getchar();
return 0;
}

Time Complexity O(nlogn)
Space Complexity O(1)
Run Here https://ideone.com/4U9JI

WAP for InOrder Predecessor In Binary Search Tree Efficiently

Data Structure Used: Binary Search Tree

Algorithm:
1.Find The Minimum value in BSt if givfen Node has the same value we are done as
the minimum value in BST is left most leaf & can't have any predecessor :)
2.Check if node->Left is leaf or not if yes then node->left is our answer
3.if n is right child then its parent will be inorder predecessor
4.else eif all aobe case fail then inorder predecessor be maximum value in left
subtree of given node N.

This Algo will take O(logn) Time in Avg.Case & O(N) time in Worst Case Skew Tree :)


#include
#include

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
struct node* parent;
};


/* Given a non-empty binary search tree, return the maximumdata
value found in that tree. Note that the entire tree does not need
to be searched. */
struct node* minValue(struct node* node);

int isLeaf(struct node* root)
{
if(root->left==NULL && root->right==NULL)
return 1;
return 0;
}


/* Given a non-empty binary search tree, return the maximumdata
value found in that tree. Note that the entire tree does not need
to be searched. */
struct node* maxValue(struct node* node)
{
struct node* current = node;

/* loop down to find the leftmost leaf */
while (current->right!= NULL) {
current = current->right;
}
return current;
}


struct node* inOrderPredecessor(struct node *root, struct node *n)
{
// step 1 of the above algorithm

if(n==minValue(root))
{
printf("No Inorder Predecessor Possible");
return NULL;
}

//2nd step of above algo

//if(n->left->data==maxValue(root))
//return n->left->data;

if(isLeaf(n->left))
return n->left;

//3rd step if n is right children of parent
struct node *p =n->parent;
if(n == p->right)
return p;

// step 4 of the above algorithm if all above not satisfied then predecessor exist in right
return maxValue(n->left);

}

/* Given a non-empty binary search tree, return the minimum data
value found in that tree. Note that the entire tree does not need
to be searched. */
struct node* minValue(struct node* node)
{
struct node* current = node;

/* loop down to find the leftmost leaf */
while (current->right != NULL) {
current = current->right;
}
return current;
}

/* Helper function that allocates a new node with the given data and
NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
node->parent = NULL;

return(node);
}

/* Give a binary search tree and a number, inserts a new node with
the given number in the correct place in the tree. Returns the new
root pointer which the caller should then use (the standard trick to
avoid using reference parameters). */

struct node* insert(struct node* node, int data)
{
/* 1. If the tree is empty, return a new,
single node */
if (node == NULL)
return(newNode(data));
else
{
struct node *temp;

/* 2. Otherwise, recur down the tree */
if (data <= node->data)
{
temp = insert(node->left, data);
node->left = temp;
temp->parent= node;
}
else
{
temp = insert(node->right, data);
node->right = temp;
temp->parent = node;
}

/* return the (unchanged) node pointer */
return node;
}
}

/* Driver program to test above functions*/
int main()
{
struct node* root = NULL, *t1,*t2,*t3,*t4, *s1,*s2,*s3,*s4 ;

//creating the tree given in the above diagram
root = insert(root, 6);
root = insert(root, 4);
root = insert(root, 13);
root = insert(root, 2);
root = insert(root, 5);
root = insert(root, 11);
root = insert(root, 14);
root = insert(root, 1);
root = insert(root, 3);
root = insert(root, 8);
root = insert(root, 9);
root = insert(root, 12);
root = insert(root, 10);

t3 = root->right->left;

/*t1 = root->left->left;
t2 = root->left->right;
t3 = root->right->left;
t4 = root->right->right;


s1 = inOrderPredecessor(root, t1);
if(s1 != NULL)
printf("\n Inorder Predecessor of %d is %d ", t1->data, s1->data);

s2 = inOrderPredecessor(root, t2);
if(s2 != NULL)
printf("\n Inorder Predecessor of %d is %d ", t2->data, s2->data);


s3 = inOrderPredecessor(root, t3);
if(s3 != NULL)
printf("\n Inorder Predecessor of %d is %d ", t3->data, s3->data);


s4 = inOrderPredecessor(root, t4);
if(s4 != NULL)
printf("\n Inorder Predecessor of %d is %d ", t4->data, s4->data);

*/


s3 = inOrderPredecessor(root, t3);
if(s3 != NULL)
printf("\n Inorder Predecessor of %d is %d ", t3->data, s3->data);


getchar();
return 0;
}

its due to insertion take o(nlogn)
Time Complexity O(NlogN) findPredecessor Will Take O(logn) in Avg. & O(N) in worst
Space Complexity O(1)
Run Here https://ideone.com/BJCtg


2nd Method Without Using Parent Pointer (Optimize Version)

#include
#include

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
struct node* parent;
};


/* Given a non-empty binary search tree, return the maximumdata
value found in that tree. Note that the entire tree does not need
to be searched. */
struct node* maxValue(struct node* node)
{
struct node* current = node;

/* loop down to find the leftmost leaf */
while (current->right!= NULL) {
current = current->right;
}
return current;
}

/* Helper function that allocates a new node with the given data and
NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
node->parent = NULL;

return(node);
}

struct node * inOrderPredecessor(struct node *root, struct node *n)
{
if( n->left != NULL )
return maxValue(n->left);
struct node *pred=NULL;
while(root)
{
if(n->data < root->data)
root=root->left;
else if(n->data > root->data)
{
pred=root;
root=root->right;
}
else
break;
}
return pred;
}
/* Give a binary search tree and a number, inserts a new node with
the given number in the correct place in the tree. Returns the new
root pointer which the caller should then use (the standard trick to
avoid using reference parameters). */
struct node* insert(struct node* node, int data)
{
/* 1. If the tree is empty, return a new,
single node */
if (node == NULL)
return(newNode(data));
else
{
/* 2. Otherwise, recur down the tree */
if (data <= node->data)
node->left = insert(node->left, data);
else
node->right = insert(node->right, data);

/* return the (unchanged) node pointer */
return node;
}
}

/* Driver program to test above functions*/
int main()
{
struct node* root = NULL, *temp, *succ, *min;

//creating the tree given in the above diagram
root = insert(root, 20);
root = insert(root, 8);
root = insert(root, 22);
root = insert(root, 4);
root = insert(root, 12);
root = insert(root, 10);
root = insert(root, 14);
temp = root->left->right->right;

succ = inOrderPredecessor(root, temp);
if(succ != NULL)
printf("\n Inorder Predecessorof %d is %d ", temp->data, succ->data);
getchar();
return 0;
}


Feel Free to Test it for More Test Cases & do notify me if it will fail :)

its due to insertion take o(nlogn)
Time Complexity O(NlogN) findPredecessor Will Take O(logn) in Avg. & O(N) in worst
Space Complexity O(1)
Run Here http://ideone.com/eKtet

Sucessor & Predecessor Algo For Tree Traversal

successor -
inorder successor of node u:
If u has a right child, r, then succ(u) is the leftmost descendent of r
Otherwise, succ(u) is the closest ancestor, v, of u (if any) such that u is descended
from the left child of v. If there is no such ancestor, then succ(u) is un defi ned.
Preorder Successor
To find the preorder successor of node u:
If u has a left child, l, then succ(u) is l.
Otherwise, if u has a right child, r, then succ(u) is r.
Otherwise, u is a leaf and the following rules apply:
if u is a left child and has a right sibling, rs, then succ(u) is rs.
otherwise, if u has an ancestor, v, which is a left-child and v has a right sibling,
vrs, then succ(u) is vrs
If there is no such ancestor, then succ(u) is undefi ned.
Postorder successor
To nd the postorder successor of node u:
If u is the root of the tree, succ(u) is unde ned.
Otherwise, if u is a right child, succ(u) is parent(u).
Otherwise u is a left child and the following applies:
if u has a right sibling, r, succ(u) is the leftmost leaf in r's subtree
otherwise succ(u) is parent(u).
Predecessor
To fi nd the inorder predecessor of node u
If u has a left child, l, then pred(u) is the rightmost descendent of l
Otherwise, pred(u) is the closest ancestor, v, of u (if any) such that u is descended
from the right child of v.
If there is no such ancestor, then pred(u) is undefi ned.
Preorder Predecessor
To find the preorder predecessor of node u:
If u is the root of the tree, then pred(u) is unde fined
If u has a left sibling, ls, then pred(u) is the rightmost descendent of ls
Otherwise, pred(u) is parent(u).

Postorder Predecessor
To nd the postorder predecessor of node u:
If u has a right child, r, then pred(u) is r.
Otherwise If u has a left child, l, then pred(u) is l.
Otherwise if u has a left sibling, ls, then pred(u) is ls
Otherwise if u has an ancestor, v, which is a right child and has a left sibling,
vls, then pred(u) is vls
Otherwise, pred(u) is unde ned.
An iterator would start with the root of the tree.

WAP to printMostFrequentCharcters..Very Important Question

You are given a function printMostFrequentWords which takes in an array of strings. You are required to print a list of all the letters that occurred with the highest frequency in each line of the file, followed by the frequency.
The list of letters should be an alphabetical list of upper case letters followed by an alphabetical list of lower case letters.
Sample Test Cases:

Input #00:
When riding your bicycle backwards down a one-way street, if the
wheel falls of a canoe, how many ball bearings does it take to fill
up a water buffalo?
Hello Howard.

Output #00:
e 6
al 7
a 3
Hlo 2

Yes This is The Exact Working Code ..Enjoy

import java.util.*;
import java.io.*;

public class ReadFileSystem
{

public static void main(String args[])throws Exception
{

BufferedReader in = new BufferedReader(new FileReader("E:/ubuntu/test.txt"));//the file containing lines.
HashMap lettercount=lettercount = new HashMap();;
String str="";

while ((str = in.readLine()) != null)
{


for (int i = 0; i < str.length(); i++)
{
Character c = str.charAt(i);

if (Character.isLetter(c))
{
if(lettercount.containsKey(c))
{

lettercount.put(c,lettercount.get(c) + new Integer(1));
}
else
{
lettercount.put(c,new Integer(1));
}
}

}


int maxCount = 0;

for(Integer count: lettercount.values())
{
if (count > maxCount)
{
maxCount = count;

}
}

StringBuffer characters =new StringBuffer();

for (Map.Entry entry: lettercount.entrySet())
{
if (entry.getValue().equals(maxCount))
{
if(entry.getKey()>='A' && entry.getKey() <='Z')
{
characters.append(entry.getKey());
characters.reverse();
}
else
characters.append(entry.getKey());

}
}
System.out.print(characters);
System.out.println(" " + maxCount);

//resetting count value
for(Map.Entry entry: lettercount.entrySet())
{
lettercount.put(entry.getKey(),0);

}


}



}

}

Cheers

A NxN binary matrix is given. If a row contains a 0 all element in the row will be set to 0 and if a column contains a 0 all element of the colum set 0

Binary Matrix Problem

Problem: An NxN binary Matrix is given. If a row contains a 0 all element in the row will be sent to 0 and if a column contains a 0 all element of the column will be set to 0. You have to do it in O(1) space.

Example:
Input array:
1 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
Result array:
0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0


Data Structure Used: 2D Array

Algorithm(Requires Two Passes Over Matrix)
1.Use two Integer or Boolean array in 1st pass over Matrix set row & col set 1 according to
content of a[i][j]
2. in second pass over matrix for all i,j check row & col array is its 1 then set a[i]j]=0 in
matrix else continue

1st Solution (Using Two Linear Boolean array of row & column)

class matrix_zero
{


public static void setZeros(int[][] matrix) {
int[] row = new int[matrix.length];
int[] column = new int[matrix[0].length];
// Store the row and column index with value 0
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length;j++) {
if (matrix[i][j] == 0) {
row[i] = 1;
column[j] = 1;
}
}
}

// Set arr[i][j] to 0 if either row i or column j has a 0
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if ((row[i] == 1 || column[j] == 1)) {
matrix[i][j] = 0;
}
}
}
}

public static void main(String a[])
{
int ar[][]=new int[][]{{1,0,1,1,0},
{0,1,1,1,0},{1,1,1,1,1},
{1,0,1,1,1},{1,1,1,1,1}
};


setZeros(ar);

for (int i = 0; i <5 data-blogger-escaped-br="" data-blogger-escaped-i=""> {
for (int j = 0; j < 5;j++)
{
System.out.println(ar[i][j]);

}
System.out.println();

}

}


}

Time Complexity O(N^2) //two Passes over Matrix
Space Complexity O(2*N)
Run Here http://ideone.com/ntrdr


2nd Solution Optimize


Algorithm: (Updated)

This method is a space optimized version of above method 1. This method uses the first row and first column of the input matrix in place of the auxiliary arrays row[] and col[] of method 1. So what we do is: first take care of first row and column and store the info about these two in two flag variables rowFlag and colFlag. Once we have this info, we can use first row and first column as auxiliary arrays and apply method 1 for submatrix (matrix excluding first row and first column) of size (M-1)*(N-1).

1) Scan the first row and set a variable rowFlag to indicate whether we need to set all 1s in first row or not.
2) Scan the first column and set a variable colFlag to indicate whether we need to set all 1s in first column or not.
3) Use first row and first column as the auxiliary arrays row[] and col[] respectively, consider the matrix as submatrix starting from second row and second column and apply method 1.
4) Finally, using rowFlag and colFlag, update first row and first column if needed.

Time Complexity: O(M*N)
Auxiliary Space: O(1)

Time Complexity O(N^2)
Space Complexity O(1)

Write A Program to Remove Duplicates from BST remember its BST not Binary Tree..

class Node{
int data;
Node left;
Node right;

Node(int data){
this.data=data;
left=null;
right=null;
}
}
class BST{
Node head;

Node insert(Node node,int data){
if(node==null)
return new Node(data);
if(data<=node.data)
node.left=insert(node.left,data);
else
node.right=insert(node.right,data);
return node;
}

public static void main(String args[]){
new BST().go();
}

void go(){
int[] a=new int[]{80,150,70,80,70,70,140,110,110};//test case
for(int i:a)
head=insert(head,i);
inorder(head);
remove(head,-1);//I need an element which cant be in the bst for a neat recursion so i use -1
System.out.println();
inorder(head);
}

void inorder(Node n){
if(n==null)
return;
inorder(n.left);
System.out.print(n.data+" ");
inorder(n.right);
}

boolean remove(Node n,int d){
if(n==null)
return false;
if(remove(n.left,n.data))
n.left=n.left.left;
if(n.data==d)
return true;
if(remove(n.right,d))
n.right=n.right.left;
return false;
}
}

Pancake Sorting (Which Uses Only Reverse Function to sort the Array)

There is an array in an external system (i.e. u cannot access the array elements directly). The system exposes 3 functions of O(1) :

length() - returns the length of the array.
get(i) - returns the element at index i.
reverse(i,j) - reverses the elements in the array from index i to index j (both indexes inclusive).

Can you sort the array in the best possible way using only these 3 operations?


Pancake sort has a direct implementation complexity of O(N2) as locating the max element in the unsorted section of the array is an O(N) operation. Besides this, it is obvious that one cannot use standard quicksort or heapsort directly since a swap operation
isn't supplied. However, we can simulate a swap operation using the reverse operator. It's easy to do:


swap(i, j) = reverse(i + 1, j) reverse(i, i+1), reverse(i+1, j) where i, j are indices to the array.


Given this swap operation, we can then implement any O(n log n) sort that we desire since we already have random access via the get(i) function.

However, we can do better:

Let us define a run as a sequence of consecutive values in the array.

1. Go through the array and reverse descending runs - O(n) as reverse(i, j) is supplied. Now you have an array with many runs in ascending order. It looks something like a0, a1 ... ak, b0, b1, ... bl, c0, c1, ... cm ...
2. Perform a merge procedure pairwise for consecutive runs in the array. The merge is performed as follows:
If a0, a1, a2 ...ak b0, b1, b2... bl are consecutive runs, then:
a) Compare a0, b0 (using get() operation to get the values).
--- Else If b0 < a0 then perform step (b). --- Else a0 is in its correct place, increment pointer to the 'a' array and repeat step 2 for a1... ak, b0 ... bl b) reverse(a0 ... b0) and then reverse (ak ... a0) - giving b0, a0, a1 ... ak, b1, b2 .. bl. Repeat step 2 for the run a0, a1 ... ak, b1, b2 ... bl Basic Approach I used Insertion Sort to Solve it First #include

/* Function to reverse arr[] from start to end*/
void rvereseArray(int arr[], int start, int end)
{

int temp;
while(start < end) { temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; } } /* Utility that prints out an array on a line */ void printArray(int arr[], int size) { int i; for (i=0; i < size; i++) printf("%d ", arr[i]); printf("\n"); } int get(int ar[],int i) { return ar[i]; } int length(int ar[]) { return (sizeof(ar)/sizeof(int)); } void sort(int arr[]) {int i,j; for( i = 1; i < 6; i++ ) { int index = i; for( j = i-1; j >= 0; j-- )
{
if( arr[j] > arr[index] )
{
rvereseArray(arr, j, index);
index = j;
}
}
}
}

/* Driver function to test above functions */
int main()
{
int arr[] = {3,1, 2, 5,4, 6};
printArray(arr, 6);

sort(arr);

printArray(arr,6);

return 0;
}

TC O(n^2)
SC O(1)
Run Here https://ideone.com/A3UUj

MOre professional Code

int pancake_sort(int *list, unsigned int length)
{
//If it's less than 2 long, just return it as sorting isn't really needed...
if(length<2) return 0; int i,a,max_num_pos,moves; moves=0; for(i=length;i>1;i--)
{
//Find position of the max number in pos(0) to pos(i)
max_num_pos=0;
for(a=0;alist[max_num_pos])
max_num_pos=a;
}

if(max_num_pos==i-1)
//It's where it need to be, skip
continue;


//Get the found max number to the beginning of the list (unless it already is)
if(max_num_pos)
{
moves++;
do_flip(list, length, max_num_pos+1);
}


//And then move it to the end of the range we're working with (pos(0) to pos(i))
moves++;
do_flip(list, length, i);

//Then everything above list[i-1] is sorted and don't need to be touched

}

return moves;
}

void do_flip(int *list, int length, int num)
{
int swap;
int i=0;
for(i;i<--num;i++) { swap=list[i]; list[i]=list[num]; list[num]=swap; } } int main(int argc, char **argv) { //Just need some random numbers. I chose <100 int list[9]; int i; srand(time(NULL)); for(i=0;i<9;i++) list[i]=rand()%100; //Print list, run code and print it again displaying number of moves printf("\nOriginal: "); print_array(list, 9); int moves = pancake_sort(list, 9, 1); printf("\nSorted: "); print_array(list, 9); printf(" - with a total of %d moves\n", moves); } //Java Working Code class PancakeSort { int[] heap; public String toString() { String info = ""; for (int x: heap) info += x + " "; return info; } public void flip(int n) { for (int i = 0; i < (n+1) / 2; ++i) { int tmp = heap[i]; heap[i] = heap[n-i]; heap[n-i] = tmp; } System.out.println("flip(0.." + n + "): " + toString()); } public int[] minmax(int n) { int xm, xM; xm = xM = heap[0]; int posm = 0, posM = 0; for (int i = 1; i < n; ++i) { if (heap[i] < xm) { xm = heap[i]; posm = i; } else if (heap[i] > xM) {
xM = heap[i];
posM = i;
}
}
return new int[] {posm, posM};
}

public void sort(int n, int dir)
{
if (n == 0) return;

int[] mM = minmax(n);
int bestXPos = mM[dir];
int altXPos = mM[1-dir];

boolean flipped = false;

if (bestXPos == n-1)
{
--n;
}
else if (bestXPos == 0)
{
flip(n-1);
--n;
}
else if (altXPos == n-1)
{
dir = 1-dir;
--n;
flipped = true;

}
else
{
flip(bestXPos);
}
sort(n, dir);

if (flipped)
{
flip(n);
}

}

PancakeSort(int[] numbers)
{
heap = numbers;
sort(numbers.length, 1);
}

public static void main(String[] args) {
int[] numbers = new int[]{5,2,3,1,4,7,6};


PancakeSort pancakes = new PancakeSort(numbers);
System.out.println(pancakes);
}
}

TC O(nlogn) See Analysis Below
SC O(1)
Run Here https://ideone.com/CoQfM



Complexity analysis:
Step 1 can be done in O(n) time. Using 2 indices to locate boundaries of runs and an O(1) reverse call, this is easy to achieve.
Step 2 The merge procedure requires 2 get() operations (one of which may be optimized away with careful coding) and (in the worst case) 2 reverse(i,j) operations. Therefore, the cost of putting 1 element in its correct position is O(1). Hence 2 sequences of lengths n and m can be merged in O(min{n, m}) swaps and O(max{n, m}) time.

Overall complexity:
Let us assume that we end up with K runs of lengths L1 - Lk from step 1. Cost of this step O(N)
Cost of merging adjacent runs = O(min{Li, Li+1}) (in terms of swaps), O(max{Li, Lj}) in terms of comparisons.
Total number of merges that will take place = K

The worst case for the problem will occur when all the arguments to min{ Li, Lj } are the same. This happens when the runs are of size N/K.
Therefore, cost of merge = O( N/K ) swaps (rather reverse(i,j) calls) and total number of merges = K. Hence overall swaps complexity is O( K * N/K ) = O( N ). However, overall comparison complexity remains O(N log N). So using the reverse operation, we've be able to optimize the number of swaps. However, we cannot breach the lower bound of Omega(n log n) for the number of comparisons required for sorting as this is a comparison based sort.

More Info http://mypages.valdosta.edu/dgibson/courses/cs3410/notes/ch08.pdf

WAPFind nth Fibonacci number Efficiently..its in O(logn)

The Fibonacci numbers are the numbers in the following integer sequence.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141, ……..

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation

F(n)=F(n-1)+F(n-2)


Method 1 ( Use recursion )
A simple method that is a direct recursive implementation mathematical recurance relation given above.

#include
int fib(int n)
{
if ( n <= 1 )
return n;
return fib(n-1) + fib(n-2);
}

int main ()
{
int n = 9;
printf("%d", fib(n));
getchar();
return 0;
}

Time Complexity: T(n) = T(n-1) + T(n-2) which is exponential.
We can observe that this implementation does a lot of repeated work (see the following recursion tree). So this is a bad implementation for nth Fibonacci number.

fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/ \
fib(1) fib(0)

Extra Space: O(n) if we consider the fuinction call stack size, otherwise O(1).

Method 2 ( Use Dynamic Programming )
We can avoid the repeated work done is the method 1 by storing the Fibonacci numbers calculated so far.
?
#include

int fib(int n)
{
/* Declare an array to store fibonacci numbers. */
int f[n+1];
int i;

/* 0th and 1st number of the series are 0 and 1*/
f[0] = 0;
f[1] = 1;

for (i = 2; i <= n; i++)
{
/* Add the previous 2 numbers in the series
and store it */
f[i] = f[i-1] + f[i-2];
}

return f[n];
}

int main ()
{
int n = 9;
printf("%d", fib(n));
getchar();
return 0;
}

Time Complexity: O(n)
Extra Space: O(n)

Method 3 ( Space Otimized Method 2 )
We can optimize the space used in method 2 by storing the previous two numbers only because that is all we need to get the next Fibannaci number in series.
?
#include
int fib(int n)
{
int a = 0, b = 1, c, i;
if( n == 0)
return a;
for (i = 2; i <= n; i++)
{
c = a + b;
a = b;
b = c;
}
return b;
}

int main ()
{
int n = 9;
printf("%d", fib(n));
getchar();
return 0;
}

Time Complexity: O(n)
Extra Space: O(1)


here another O(n) which relies on the fact that if we n times multiply the matrix M = {{1,0},{0,1}} to itself (in other words calculate power(M, n )), then we get the (n+1)th Fibonacci number as the element at 0,0 in the resultant matrix.

The matrix representation gives the following closed expression for the Fibonacci numbers:
1 1 ^n = Fn+1 Fn
1 0 Fn Fn-1


#include

/* Helper function that multiplies 2 matricies F and M of size 2*2, and
puts the multiplication result back to F[][] */
void multiply(int F[2][2], int M[2][2]);

/* Helper function that calculates F[][] raise to the power n and puts the
result in F[][]
Note that this function is desinged only for fib() and won't work as general
power function */
void power(int F[2][2], int n);

/* Helper function that multiplies 2 matricies F and M of size 2*2, and puts
the multiplication result back to F[][] */
void multiply(int F[2][2], int M[2][2]);

int fib(int n)
{
int F[2][2] = {{1,1},{1,0}};
if(n == 0)
return 0;
power(F, n-1);

return F[0][0];
}

void multiply(int F[2][2], int M[2][2])
{
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
int w = F[1][0]*M[0][1] + F[1][1]*M[1][1];

F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}

void power(int F[2][2], int n)
{
int i;
int M[2][2] = {{1,1},{1,0}};

// n - 1 times multiply the matrix to {{1,0},{0,1}}
for ( i = 2; i <= n; i++ )
multiply(F, M);
}

/* Driver program to test above function */
int main()
{
int n = 9;
printf("%d", fib(n));
getchar();
return 0;
}


Time Complexity: O(n)
Extra Space: O(1)

Method 5 ( Optimized Method 4 )
The method 4 can be optimized to work in O(Logn) time complexity. We can do recursive multiplication to get power(M, n) in the prevous method (Similar to the optimization done in this post)
?
#include

void multiply(int F[2][2], int M[2][2]);

void power(int F[2][2], int n);

/* function that returns nth Fibonacci number */
int fib(int n)
{
int F[2][2] = {{1,1},{1,0}};
if(n == 0)
return 0;
power(F, n-1);
return F[0][0];
}

/* Optimized version of power() in method 4 */
void power(int F[2][2], int n)
{
if( n == 1 )
return;
int M[2][2] = {{1,1},{1,0}};

power(F, n/2);
multiply(F, F);

if( n%2 != 0 )
multiply(F, M);
}

void multiply(int F[2][2], int M[2][2])
{
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
int w = F[1][0]*M[0][1] + F[1][1]*M[1][1];

F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}

/* Driver program to test above function */
int main()
{
int n = 9;
printf("%d", fib(9));
getchar();
return 0;
}

Time Complexity: O(Logn)
Extra Space: O(Logn) if we consider the function call stack size, otherwise O(1).


Follow Up

WAP For Generating The Series of Fibonacci Numbers . More Focused on Time & Space Complexity


As a simple rule of recursion, any function can be computed using a recursive routine if :
1. The function can be expressed in its own form.
2. There exists a termination step, the point at which f(x) is known for a particular ‘x’.

Therefore to write a recursive program to find the nth term of the fibonacci series, we have to express the fibonacci sequence in a recursive form using the above 2 rules :
1. fib(n) = fib(n-1) + fib(n-2) (recursive defination of fibonacci series).
2. if n=0 or n=1, return n (termination step).
Using these 2 rules, the recursive program for finding the nth term of the fibonacci series can be coded very easily as shown.

The exe file can be downloaded from here : FIBONACCI

#include "stdio.h"


int fib(int n)
{
if(n==1 || n==0)
return n;
return fib(n-1)+fib(n-2);

}
int main()
{
int i,r;
for(i=0;i<10;i++)
{
r=fib(i);
printf("%d %d \n",i,r);
}

return 0;
}


Here is Time Complexity Explanation as We Know Fibonacci series is like
0, 1, 1, 2, 3, 5, 8, 13, ...& so on
start form this position
fib(0)=1
fib(1)=2
fib(2) = fib(0) + fib (1) // 1 + 1 + 1 = 3 = 2^1 + 1
fib(3) = fib(1) + fib (2) // 1 + 3 + 1 = 5 = 2^2 + 1
fib(4) = fib(2) + fib(3) // 3 + 5 + 1 = 9 = 2^3 + 1



hence fib(n) - recursive calls = 2^(n-1) + 1

So O(2^n) - which is exponential complexity. Looking at the space in similar fashion for each recursive call - we get O(n)


Time Complexity O(2^n)
Space Complexity O(n)
Run Here https://ideone.com/1RlcP