WAP to Check That Binary Representation of Given Number is Palindrome of NOt

Here i Found an Algorithm for This

Algorithm
take two varible i -0 & j=N (number)
keep storing bits of number from lsb in reverse order (e.g. shift i left & do or operation with j&1 (mind shud click this the way to extract right most set bit from number :)
keep shifting j right while j is not equals to 0

Explaintion

The first while loop reverses the rightmost bits of the number, stopping after the leftmost 1-bit. It does this by anding out the low-order bit of the number j and oring it into a new number, i. Then j is shifted right. E.g., the number j = 01101 becomes 01011. If the number j matches the input number, then the input number is a palindrome, and the procedure returns TRUE. If the reversed number is less than the input number, it may be that the input number has trailing zeros. E.g., 0110 has reversal 0011. Since this is less than the input number, we shift it left until it is no longer less, giving 0110. Since this equals the input number, we call the number a palindrome. If you don't want to consider the leading zeros, then you leave out the second while loop and say that the number 0110 is not a palindrome.


#include

bool isPalindrome(int N)
{
int i = 0, j = N;
while(j)
{
i = (i << 1) | (j & 1); j >>= 1;
}
return(i == N);
}

int main()
{
printf( " %d ", isPalindrome(9));

}


TC O(logn) as You Know that n=logk(base 2)
Sc O(1)
Run Here http://ideone.com/ddovS


Most Optimized Way can Be Find Here http://www-graphics.stanford.edu/~seander/bithacks.html#BitReverseTable in O(1) :)

WAP to convert a given string to its palindrome string by appending min chars at the right side of string.

Example
e.g. i/p is abc , o/p should be abcba
i/p is aaba , o/p should be aabaa.

aaba is not a palindrome

aaaa is a palindorme (so it does not require anything)

aabaa is also a palindrome (so it does not require anything)

Example 1:
-------------
str = abcbad;
revStr = dabcba;
output = abcbadabcba

Example 2:
----------------
str = abcb;
revStr = bcba;
output = abcba;

Ecample 3
str = rrrr
revstr=rrrr
output=rrrr

WAP to Calculate the next Smallest Prime Number From Given Number Efficiently

Given a number n, compute the smallest prime that is bigger than n. For example, n=8, then the smallest prime that bigger than 8 is 11. n=23 o/p is 29 & so on

#include

int power(int x, int y)
{
int temp;
if( y == 0)
return 1;
temp = power(x, y/2);
if (y%2 == 0)
return temp*temp;
else
return x*temp*temp;
}


double sqrt(const double s)
{

double xn = s / 2.0;
double lastX = 0.0;

// Looping this way ensures we perform only as many calculations as necessary.
// Can be replaced with a static for loop if you really want to.
while(xn != lastX) {
lastX = xn;
xn = (xn + s/xn) / 2.0;
}

return xn;

}
bool is_prime(int x)
{
if(x <= 1)
return false;
int s = (int) sqrt(x);
for(int i = 2; i <= s; i++)
if(x%i == 0)
return false;
return true;
}

int next_prime(int n)
{
int i=n+1;


/*The largest known Mersenne prime (243,112,609 − 1) is also the largest known prime
number,else // no such prime exist explain above
int pow=power(2,243112609)−1;
if(n>pow)
return 0; this line wont execute overflow*/

while(true)
{

if(is_prime(i))
break;
i++;

}
return i;
}
int main()
{
printf( " %d ", next_prime(23));
return 0;

}


TC of isprime is O(sqrt(n))
TC of sqrt is log(n)
TC of pow function is O(logn)
TC of next prime O(k*sqrt(n) where k is number of iteration used to find next smallest prime so k is constant & so overall time complexity of this algo is O(sqrt(n))

TC O(sqrt(n))
SC O(1)
Run Here https://ideone.com/5ViQe

Feel Free to Comment or Optimize the solution or if any issue with time complexity

WAP to Concatenating the Two String while removing duplicate characters Efficiently

Given two strings s1 and s2, s1 has some characters at the end which are same as some of s2's starting characters, so you have to concatenate the strings so that the repeated portion occurs only once.

ex: S1="ABCDEFGHIJK"
S2="GHIJKXYZ"

OUTPUT="ABCDEFGHIJKXYZ"


#include
#include
int main()
{
char s1[] ="ABCDEFGHIJK";//"ABCDCDEF";
char s2[]="GHIJKXYZ";// "CDEFGHI";
char s3[100];
char *p1;
char *p2;
p1= s1;
p2 =s2;
int i =0;
while(*p1 )
{
if(*p1 != *p2)
{
s3[i++] = *p1;
p1++;

}
if(*p1 == *p2)
{
s3[i++] = *p1;
p1++;
p2++;
}

}
while(*p2)
{
s3[i++] = *p2;
p2++;
}
s3[i] = '\0';
printf("string is %s",s3);
getchar();
}

Run Here https://ideone.com/Y1yGb

WAP to Implement String reverse function using Bit Manipulation

#include

/* Function to reverse str[] from start to end*/
void rverese(char str[], int start, int end)
{
char temp;
while(start < end)
{
/* swap str[start] and str[end]*/
if(str[start]!= str[end])
{
str[start] ^= str[end];
str[end] ^= str[start];
str[start] ^= str[end];
}

start++;
end--;
}
}

int main()
{
char str[] = "CrackingTheCode";
printf("Original string is %s\n", str);
rverese(str, 0, 12);
printf("Reversed string is %s\n", str);
getchar();
return 0;
}

TC O(n)
SC O(1)
Run Here https://ideone.com/j673O


2nd Method

#include


int main()
{
char ip[10];
char op[10];
char *p,*q;

scanf("%s",ip);
p=ip;
q=op;

//point p to last character of i/p string
while(*(++p)!='\0');
p--;

//now p piinte to last & s points to start of i/p string so copy from p to q
//and now q will contain the reverse of original string

while(p!=ip)
{
*(q++)=*(p--);
}
*(q++)=*(p--); // first character of string
*q='\0';

printf("%s",op);
return 0;
}

TC O(N)
SC O(1)
Run Here https://ideone.com/MkDDs

WAP to Calculate The Power x^n Efficiently in O(logn)

Method 1 Using Iterative Method

#include
main()
{
int num, p , result;
printf("Enter the number : ");
scanf("%d",&num);
printf("\nAnd its power also. : ");
scanf("%d",&p);

result = power(num,p);
printf("\nThe result is %d\n", result);
}
power(int x, int y)
{
int i,temp =1;
if(y==0)
return(1);
if(y==1)
return(x);
else
{
for(i=1;i<=y;i++)
temp = temp*x;
return(temp);
}
}

Method 2 Using Recursion

Below solution divides the problem into subproblems of size y/2 and call the subproblems recursively.


#include

/* Function to calculate x raised to the power y */
int power(int x, unsigned int y)
{
if( y == 0)
return 1;
else if (y%2 == 0)
return power(x, y/2)*power(x, y/2);
else
return x*power(x, y/2)*power(x, y/2);

}

/* Program to test function power */
int main()
{
int x = 2;
unsigned int y = 3;

printf("%d", power(x, y));
getchar();
return 0;
}

Time Complexity: O(n)
Space Complexity: O(1)
Algorithmic Paradigm: Divide and conquer.

Method 3 Reducing Instruction to Nearly Half

Above function can be optimized to O(logn) by calculating power(x, y/2) only once and storing it.

/* Function to calculate x raised to the power y in O(logn)*/
int power(int x, unsigned int y)
{
int temp;
if( y == 0)
return 1;
temp = power(x, y/2);
if (y%2 == 0)
return temp*temp;
else
return x*temp*temp;
}

Time Complexity of optimized solution: O(logn)

Method 4 case handled for -Ive Number

Let me extend the pow function to work for negative y and float x.

/* Extended version of power function that can work
for float x and negative y*/
#include

float power(float x, int y)
{
float temp;
if( y == 0)
return 1;
temp = power(x, y/2);
if (y%2 == 0)
return temp*temp;
else
{
if(y > 0)
return x*temp*temp;
else
return (temp*temp)/x;
}
}

/* Program to test function power */
int main()
{
float x = 2;
int y = -3;
printf("%f", power(x, y));
getchar();
return 0;
}

Method 5 Power calculation Using + and - Operator Only

#include



/* assumption: y is greater than or equal to 0*/
int multiply(int x, int y)
{
if(y)
return (x + multiply(x, y-1));
return 0;
}
/* assumption: b is greater than or equal to 0*/
int pow(int a, int b)
{
if(b)
return multiply(a, pow(a, b-1));
return 1;
}
int main()
{
printf("\n %d", pow(3, 2));
getchar();
return 0;
}


Time Complexity O(n)
Space Complexity O(n) if Stack Space else O(1)

Run Here https://ideone.com/BBdU1

Write a function that computes log2() using sqrt().

Well Its Very Interesting &n Tough Question Unless You Think ..Most of Us Stuck Whats The Use of Sqrt(0 to calculate log2() ..isn't it..?? i also stuck 1st but after doing some stuff with maths i was able to come up with this Algorithm so It Can be Done Using Simple Maths

As we Know

sqrt(x) = x^1/2

ln2(x) = ln(x) / ln(2)

ln2(sqrt(x)) = ln( x^(1/2) ) / ln(2)
= ((1/2) ln(x)) / ln(2)
= (1/2) * ln2(x)

So ln2(x) = 2 * ln2(sqrt(x))




class log_2
{

static double ln2;
static double epsilon = 0.0000001;

public static void main(String[] args)
{

ln2 = Math.log(2);

System.out.println("log2(10) = " + log2(10));
System.out.println("log2(10) = " + Math.log(10)/ln2);

}

public static double log2(double x)
{
if( x - 1 < epsilon ){

return (x-1)/ln2;
}
else{

return log2( Math.sqrt(x) ) * 2;
}
printf( " %d ", x/2);
}
}


Correctness Depends on epsilon value e.g no of places after decimal
Expected Output log2(10) = 3.3219282055116603
Actual Output log2(10) = 3.3219280948873626



Also You Know Taylor Series Extension of Log(1+x)= x - x^2/2 + x^3/3 + ... + ((-1)^(i+1).x^i)/i + o(x^(i+1))

More info http://en.wikipedia.org/wiki/Binary_logarithm

WAP to Implement Queue Using Stack Efficiently

A queue can be implemented using two stacks. Let queue to be implemented be q and stacks used to implement q be stack1 and stack2. q can be implemented in two ways:

Method 1 (By making enQueue operation costly)
This method makes sure that newly entered element is always at the top of stack 1, so that deQueue operation just pops from stack1. To put the element at top of stack1, stack2 is used.

enQueue(q, x)
1) While stack1 is not empty, push everything from satck1 to stack2.
2) Push x to stack1 (assuming size of stacks is unlimited).
3) Push everything back to stack1.

dnQueue(q)
1) If stack1 is empty then error
2) Pop an item from stack1 and return it

Method 2 (By making deQueue operation costly)
In this method, in en-queue operation, the new element is entered at the top of stack1. In de-queue operation, if stack2 is empty then all the elements are moved to stack2 and finally top of stack2 is returned.

enQueue(q, x)
1) Push x to stack1 (assuming size of stacks is unlimited).

deQueue(q)
1) If both stacks are empty then error.
2) If stack2 is empty
While stack1 is not empty, push everything from satck1 to stack2.
3) Pop the element from stack2 and return it.

Method 2 is definitely better than method 1. Method 1 moves all the elements twice in enQueue operation, while method 2 (in deQueue operation) moves the elements once and moves elements only if stack2 empty.

Implementation of method 1


Implementation of method 2

/* Program to implement a queue using two stacks */
#include
#include

/* structure of a stack node */
struct sNode
{
int data;
struct sNode *next;
};

/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data);

/* Function to pop an item from stack*/
int pop(struct sNode** top_ref);

/* structure of queue having two stacks */
struct queue
{
struct sNode *stack1;
struct sNode *stack2;
};

/* Function to enqueue an item to queue */
void enQueue(struct queue *q, int x)
{
push(&q->stack1, x);
}

/* Function to dequeue an item from queue */
int deQueue(struct queue *q)
{
int x;

/* If both stacks are empty then error */
if(q->stack1 == NULL && q->stack2 == NULL)
{
printf("Q is empty");
getchar();
exit(0);
}

/* Move elements from satck1 to stack 2 only if
stack2 is empty */
if(q->stack2 == NULL)
{
while(q->stack1 != NULL)
{
x = pop(&q->stack1);
push(&q->stack2, x);
}
}

x = pop(&q->stack2);
return x;
}

/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data)
{
/* allocate node */
struct sNode* new_node =
(struct sNode*) malloc(sizeof(struct sNode));

if(new_node == NULL)
{
printf("Stack overflow \n");
getchar();
exit(0);
}

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */
new_node->next = (*top_ref);

/* move the head to point to the new node */
(*top_ref) = new_node;
}

/* Function to pop an item from stack*/
int pop(struct sNode** top_ref)
{
int res;
struct sNode *top;

/*If stack is empty then error */
if(*top_ref == NULL)
{
printf("Stack overflow \n");
getchar();
exit(0);
}
else
{
top = *top_ref;
res = top->data;
*top_ref = top->next;
free(top);
return res;
}
}

/* Driver function to test anove functions */
int main()
{
/* Create a queue with items 1 2 3*/
struct queue *q = (struct queue*)malloc(sizeof(struct queue));
q->stack1 = NULL;
q->stack2 = NULL;
enQueue(q, 1);
enQueue(q, 2);
enQueue(q, 3);

/* Dequeue items */
printf("%d ", deQueue(q));
printf("%d ", deQueue(q));
printf("%d ", deQueue(q));

getchar();
}

Run here https://ideone.com/fafrK

WAP to Implement Stack using Queue Efficiently

It Can be Done using two Strategy by making push or pop oeration costly

Method A: By making Push Operation Costly
* push:
o if q1 is empty then simply add the item & return
else if q1 is not empty enqueue all items of queue1 in queue2, & then
enqueue given element in queue1
o Then enqueue all items from q2 to q1 again
this way names of queue1 and queue2
* pop:
o deqeue from queue1


Method B: By making Pop Operation Costly
* push:
o enqueue in queue1
* pop:
o while size of queue1 is bigger than 1, pipe dequeued items
from queue1 into queue2
o dequeue and return the last item of queue1, then switch the
names of queue1 and queue2



Obvious 2nd method is best because 1st moves all the element twice in in push operation

1st method implementation

import java.util.*;

class StackUsingQueues
{


Queue q1 = new LinkedList();
Queue q2 = new LinkedList();

public int pop()
{
if (q1.peek() == null) {
System.out.println("The stack is empty, nothing to return");
int i = 0;
return i;
} else {
int pop = q1.remove();
return pop;

}
}

public void push(int data) {

if (q1.peek() == null) {
q1.add(data);
} else {
for (int i = q1.size(); i > 0; i--) {
q2.add(q1.remove());
}
q1.add(data);
for (int j = q2.size(); j > 0; j--) {
q1.add(q2.remove());
}

}
}

public static void main(String[] args) {
StackUsingQueues s1 = new StackUsingQueues();
// Stack s1 = new Stack();
s1.push(1);
s1.push(2);
s1.push(3);
s1.push(4);
s1.push(5);
s1.push(6);
s1.push(7);

// s1.push(6);
System.out.println("1st = " + s1.pop());
System.out.println("2nd = " + s1.pop());
System.out.println("3rd = " + s1.pop());
System.out.println("4th = " + s1.pop());
System.out.println("5th = " + s1.pop());
System.out.println("6th = " + s1.pop());
System.out.println("7th = " + s1.pop());

}

}

2nd method--Need to Modify

import java.util.*;

class StackUsingQueues
{


Queue q1 = new LinkedList();
Queue q2 = new LinkedList();

public int pop()
{
if(q1.peek() == null)
{
System.out.println("The stack is empty, nothing to return");
int i = 0;
return i;
}
else
{
while(q1.size()>q2.size())
{
q2.add(q1.remove());
}
int size=1,pop=0;
while(size!=q1.size())
{
pop=q1.remove();
size++;
}

while(!q2.isEmpty())
{
q1.add(q2.remove());
}

return pop;

}
//return 0;
}

public void push(int data)
{
q1.add(data);
}

boolean emptys(Queue q)
{
return (q.size()==0);

}
public static void main(String[] args) {
StackUsingQueues s1 = new StackUsingQueues();

s1.push(1);
s1.push(2);
s1.push(3);
s1.push(4);
s1.push(5);
s1.push(6);
s1.push(7);

// s1.push(6);
System.out.println("1st = " + s1.pop());
System.out.println("2nd = " + s1.pop());
System.out.println("3rd = " + s1.pop());
System.out.println("4th = " + s1.pop());
System.out.println("5th = " + s1.pop());
System.out.println("6th = " + s1.pop());
System.out.println("7th = " + s1.pop());

}

}

Run here https://ideone.com/K1a3C

WAP to Find majority Eelement In Linked lIst In One Pass

you hve a linked list of unknown length n. there is an element which is repeated more than n/2 number of times. find that element... you should use constant extra space and can make only one pass over the list.....

#include
#include
struct node
{
int data;
struct node *next;
};

struct node *head = NULL;
struct node *tail = NULL;

int push(int input)
{
struct node *newnode = (struct node *)malloc(sizeof(struct node));
if(!newnode) return 0;
newnode->data = input;
if(tail) {
tail->next = newnode;
}
newnode->next = NULL;
tail = newnode;
if(!head) head = newnode;
return 1;
}

int display()
{
struct node *current = head;
while(current)
{
printf("%d\n", current->data);
current = current->next;
}
}

int freenodes()
{
struct node *current = head;
if(head) head = head->next;
while(current)
{
free(current);
current = head;
if(head) head = head->next;
}
printf("Linked List Freed\n");
}

int findmaxrepeat()
{
if(!head) return 0;
struct node *current = head->next;
int value = 0;
int count = 0;
int maxvalue = 0;
int maxvaluecnt = 0;
value = head->data; count +=1;
maxvalue = value;
maxvaluecnt = count;
while(current)
{
if(current->data == value) count +=1;
else
{
if(maxvaluecnt < count) { maxvaluecnt = count; maxvalue = value;}
value = current->data; count = 1;
}
current = current->next;
}
return maxvalue;
}

int main()
{
push(1);
push(3);
push(2);
push(3);
push(3);
push(1);
push(1);
push(3);
push(3);
push(1);
push(3);
display();
printf("%d is the maxrepeated value\n", findmaxrepeat());
freenodes();
}

TC O(n)
SC O(1)
Run Here https://ideone.com/qmu7Z

WAP to Find majority Eelement In Linked lIst In One Pass

you hve a linked list of unknown length n. there is an element which is repeated more than n/2 number of times. find that element... you should use constant extra space and can make only one pass over the list.....

#include
#include
struct node
{
int data;
struct node *next;
};

struct node *head = NULL;
struct node *tail = NULL;

int push(int input)
{
struct node *newnode = (struct node *)malloc(sizeof(struct node));
if(!newnode) return 0;
newnode->data = input;
if(tail) {
tail->next = newnode;
}
newnode->next = NULL;
tail = newnode;
if(!head) head = newnode;
return 1;
}

int display()
{
struct node *current = head;
while(current)
{
printf("%d\n", current->data);
current = current->next;
}
}

int freenodes()
{
struct node *current = head;
if(head) head = head->next;
while(current)
{
free(current);
current = head;
if(head) head = head->next;
}
printf("Linked List Freed\n");
}

int findmaxrepeat()
{
if(!head) return 0;
struct node *current = head->next;
int value = 0;
int count = 0;
int maxvalue = 0;
int maxvaluecnt = 0;
value = head->data; count +=1;
maxvalue = value;
maxvaluecnt = count;
while(current)
{
if(current->data == value) count +=1;
else
{
if(maxvaluecnt < count) { maxvaluecnt = count; maxvalue = value;}
value = current->data; count = 1;
}
current = current->next;
}
return maxvalue;
}

int main()
{
push(1);
push(3);
push(2);
push(3);
push(3);
push(1);
push(1);
push(3);
push(3);
push(1);
push(3);
display();
printf("%d is the maxrepeated value\n", findmaxrepeat());
freenodes();
}

WAP to Find Majority Element In Sorted Array Ofcourse It Shoud be Done in O(logn)

/* Program to check for majority element in a sorted array */
#include
# define bool int

/* If x is present in arr[low...high] then returns the index of
first occurance of x, otherwise returns -1 */
int _binarySearch(int arr[], int low, int high, int x);

/* This function returns true if the x is present more than n/2
times in arr[] of size n */
bool isMajority(int arr[], int n, int x)
{
int i = _binarySearch(arr, 0, n-1, x);
printf ( " %d ", i);

/* check if the element is present more than n/2 times */
if(((i + n/2) <= (n -1)) && arr[i + n/2] == x)
return 1;
else
return 0;
}

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

/* Check if arr[mid] is the first occurrence of x.
arr[mid] is first occurrence if x is one of the following
is true:
(i) mid == 0 and arr[mid] == x
(ii) arr[mid-1] < x and arr[mid] == x
*/
if(( mid == 0 || x > arr[mid-1]) && (arr[mid] == x))
return mid;
else if(x > arr[mid])
return _binarySearch(arr, (mid + 1), high, x);
else
return _binarySearch(arr, low, (mid -1), x);
}

/*Return -1 if element does not appear more than n/2 times*/
return -1;
}

/* Driver program to check above functions */
int main()
{
int arr[] = {1, 3, 3, 3,3,4,10};//sorted
int n = 7;
int x = 3;
if(isMajority(arr, n, x))
printf("%d appears more than %d times in arr[]", x, n/2);
else
printf("%d does not appear more than %d times in arr[]", x, n/2);

getchar();
return 0;
}

Time Complexity O(logn)
Space Complexity O(1)
Run Here https://ideone.com/kEdi4

WAP to Find Two elements in Array whose sum is closest to zero

Algorithm
1) Sort all the elements of the array.
2) Find the index of first positive element, this is initial value of right index r.
3) Initialize: left index l = r – 1. min_sum = INT_MIN
4) In a loop, look for the candidates by comparing sum with minimum sum. If arr[l] + arr[r] becomes negative then increment the right index r, else decrement left index l.

#include
#include
#include


void quickSort(int *, int, int);

/* Function to print pair of elements having minimum sum */
void minAbsSumPair(int arr[], int arr_size)
{
int l, r = 0, min_sum, sum = 0, min_l, min_r;

/* Array should have at least two elements*/
if(arr_size < 2)
{
printf("Invalid Input");
return;
}

/* Sort the elements */
quickSort(arr, 0, arr_size-1);

/* Find the first positive element. Note that we have condition "r < arr_size -1"
-1 is there to handle the cases when all elements are negative */
while(arr[r] < 0 && r < arr_size - 1)
r++;

/* If all elements are positive then first two elements
are the minimum sum elements */
if(r == 0)
{
printf(" The first two elements %d and %d have minimum sum",
arr[0], arr[1]);
return;
}

/* Start looking for the pair from the first positive element
and last negative element */
l = r - 1;
min_sum = arr[l] + arr[r];
min_l = l; /* min_l is for the left element of minimum sum pair*/
min_r = r; /* min_r is for the right element of minimum sum pair*/
while(l >= 0 && r < arr_size)
{
sum = arr[l] + arr[r];

/*If abs(sum) is less then update the result items*/
if(abs(sum) < abs(min_sum))
{
min_sum = sum;
min_l = l;
min_r = r;
}
if(sum < 0)
r++;
else
l--;

printf (" %d %d %d \n ",min_sum,l,r);
}

printf(" The two elements whose sum is minimum are %d and %d",
arr[min_l], arr[min_r]);
}

/* Driver program to test above function */
int main()
{
int arr[] = {1, 60, -10, 70, -80, 85};
minAbsSumPair(arr, 6);
getchar();
return 0;
}

/* FOLLOWING FUNCTIONS ARE ONLY FOR SORTING
PURPOSE */
void exchange(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}

int partition(int arr[], int si, int ei)
{
int x = arr[ei];
int i = (si - 1);
int j;

for (j = si; j <= ei - 1; j++)
{
if(arr[j] <= x)
{
i++;
exchange(&arr[i], &arr[j]);
}
}

exchange (&arr[i + 1], &arr[ei]);
return (i + 1);
}

/* Implementation of Quick Sort
arr[] --> Array to be sorted
si --> Starting index
ei --> Ending index
*/
void quickSort(int arr[], int si, int ei)
{
int pi; /* Partitioning index */
if(si < ei)
{
pi = partition(arr, si, ei);
quickSort(arr, si, pi - 1);
quickSort(arr, pi + 1, ei);
}
}

Tim Complexity O(nlogn)
Space Complexity O(1)
Run Here https://ideone.com/Y4sk0

WAP to Find Median of Two Sorted Array in O(logn) Time

There are 2 sorted arrays A and B of size n each. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n))


Median: In probability theory and statistics, a median is described as the number separating the higher half of a sample from the lower half.
The median of a finite list of numbers can be found by arranging all the numbers from lowest value to highest value and picking the middle one.

For getting the median of input array { 12, 11, 15, 10, 20 }, first sort the array. We get { 10, 11, 12, 15, 20 } after sorting. Median is the middle element of the sorted array which is 12.

Algo 1 merge both array & return avg of a[n/2]+a[n/2-1]/2;but merging requires extra space of size O(2n)

Algo 2 Linear Time O(n)

Use merge procedure of merge sort. Keep track of count while comparing elements of two arrays. If count becomes n(For 2n elements), we have reached the median. Take the average of the elements at indexes n-1 and n in the merged array. See the below implementation.

if (i==n) base case when all elements of 1st array is less then 1st element of 2nd Array
then m1=m2;
m2=a[0];//obvious
break

if(j==n)
base case when all elements of 2nd array is less then 1st element of 1st Array
then
m1=m2;
m2=a1[0]; //obvious
& break



#include

/* This function returns median of ar1[] and ar2[].
Assumptions in this function:
Both ar1[] and ar2[] are sorted arrays
Both have n elements */
int getMedian(int ar1[], int ar2[], int n)
{
int i = 0; /* Current index of i/p array ar1[] */
int j = 0; /* Current index of i/p array ar2[] */
int count;
int m1 = -1, m2 = -1;

/* Since there are 2n elements, median will be average
of elements at index n-1 and n in the array obtained after
merging ar1 and ar2 */
for(count = 0; count <= n; count++)
{
/*Below is to handle case where all elements of ar1[] are
smaller than smallest(or first) element of ar2[]*/
if(i == n)
{
m1 = m2;
m2 = ar2[0];
break;
}

/*Below is to handle case where all elements of ar2[] are
smaller than smallest(or first) element of ar1[]*/
else if(j == n)
{
m1 = m2;
m2 = ar1[0];
break;
}

if(ar1[i] < ar2[j])
{
m1 = m2; /* Store the prev median */
m2 = ar1[i];
i++;
}
else
{
m1 = m2; /* Store the prev median */
m2 = ar2[j];
j++;
}
}

return (m1 + m2)/2;
}

/* Driver program to test above function */
int main()
{
int ar1[] = {1, 12, 15, 26, 38};
int ar2[] = {2, 13, 17, 30, 45};

printf("%d", getMedian(ar1, ar2, 5)) ;

getchar();
return 0;
}

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

3rd Algo O(logn)

This method works by first getting medians of the two sorted arrays and then comparing them.

Let ar1 and ar2 be the input arrays.

Algorithm:

1) Calculate the medians m1 and m2 of the input arrays ar1[]
and ar2[] respectively.
2) If m1 and m2 both are equal then we are done.
return m1 (or m2)
3) If m1 is greater than m2, then median is present in one
of the below two subarrays.
a) From first element of ar1 to m1 (ar1[0...|_n/2_|])
b) From m2 to last element of ar2 (ar2[|_n/2_|...n-1])
4) If m2 is greater than m1, then median is present in one
of the below two subarrays.
a) From m1 to last element of ar1 (ar1[|_n/2_|...n-1])
b) From first element of ar2 to m2 (ar2[0...|_n/2_|])
5) Repeat the above process until size of both the subarrays
becomes 2.
6) If size of the two arrays is 2 then use below formula to get
the median.
Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2

Example:

ar1[] = {1, 12, 15, 26, 38}
ar2[] = {2, 13, 17, 30, 45}

For above two arrays m1 = 15 and m2 = 17

For the above ar1[] and ar2[], m1 is smaller than m2. So median is present in one of the following two subarrays.

[15, 26, 38] and [2, 13, 17]

Let us repeat the process for above two subarrays:

m1 = 26 m2 = 13.

m1 is greater than m2. So the subarrays become

[15, 26] and [13, 17]
Now size is 2, so median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
= (max(15, 13) + min(26, 17))/2
= (15 + 17)/2
= 16


#include

/* This function returns median of ar1[] and ar2[].
Assumptions in this function:
Both ar1[] and ar2[] are sorted arrays
Both have n elements */
int getMedian(int ar1[], int ar2[], int n)
{
int i = 0; /* Current index of i/p array ar1[] */
int j = 0; /* Current index of i/p array ar2[] */
int count;
int m1 = -1, m2 = -1;

/* Since there are 2n elements, median will be average
of elements at index n-1 and n in the array obtained after
merging ar1 and ar2 */
for(count = 0; count <= n; count++)
{
/*Below is to handle case where all elements of ar1[] are
smaller than smallest(or first) element of ar2[]*/
if(i == n)
{
m1 = m2;
m2 = ar2[0];
break;
}

/*Below is to handle case where all elements of ar2[] are
smaller than smallest(or first) element of ar1[]*/
else if(j == n)
{
m1 = m2;
m2 = ar1[0];
break;
}

if(ar1[i] < ar2[j])
{
m1 = m2; /* Store the prev median */
m2 = ar1[i];
i++;
}
else
{
m1 = m2; /* Store the prev median */
m2 = ar2[j];
j++;
}
}

return (m1 + m2)/2;
}

/* Driver program to test above function */
int main()
{
int ar1[] = {1, 12, 15, 26, 38};
int ar2[] = {2, 13, 17, 30, 45};

printf("%d", getMedian(ar1, ar2, 5)) ;

getchar();
return 0;
}


Time Complexity O(logn)
Space Complexity O(1)
Run Here https://ideone.com/ZE4Vq

Complete Reference From G4G & http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf

WAP to Find Median of Two Sorted Array in O(logn) Time

There are 2 sorted arrays A and B of size n each. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n))


Median: In probability theory and statistics, a median is described as the number separating the higher half of a sample from the lower half.
The median of a finite list of numbers can be found by arranging all the numbers from lowest value to highest value and picking the middle one.

For getting the median of input array { 12, 11, 15, 10, 20 }, first sort the array. We get { 10, 11, 12, 15, 20 } after sorting. Median is the middle element of the sorted array which is 12.

Algo 1 merge both array & return avg of a[n/2]+a[n/2-1]/2;but merging requires extra space of size O(2n)

Algo 2 Linear Time O(n)

Use merge procedure of merge sort. Keep track of count while comparing elements of two arrays. If count becomes n(For 2n elements), we have reached the median. Take the average of the elements at indexes n-1 and n in the merged array. See the below implementation.

if (i==n) base case when all elements of 1st array is less then 1st element of 2nd Array
then m1=m2;
m2=a[0];//obvious
break

if(j==n)
base case when all elements of 2nd array is less then 1st element of 1st Array
then
m1=m2;
m2=a1[0]; //obvious
& break



#include

/* This function returns median of ar1[] and ar2[].
Assumptions in this function:
Both ar1[] and ar2[] are sorted arrays
Both have n elements */
int getMedian(int ar1[], int ar2[], int n)
{
int i = 0; /* Current index of i/p array ar1[] */
int j = 0; /* Current index of i/p array ar2[] */
int count;
int m1 = -1, m2 = -1;

/* Since there are 2n elements, median will be average
of elements at index n-1 and n in the array obtained after
merging ar1 and ar2 */
for(count = 0; count <= n; count++)
{
/*Below is to handle case where all elements of ar1[] are
smaller than smallest(or first) element of ar2[]*/
if(i == n)
{
m1 = m2;
m2 = ar2[0];
break;
}

/*Below is to handle case where all elements of ar2[] are
smaller than smallest(or first) element of ar1[]*/
else if(j == n)
{
m1 = m2;
m2 = ar1[0];
break;
}

if(ar1[i] < ar2[j])
{
m1 = m2; /* Store the prev median */
m2 = ar1[i];
i++;
}
else
{
m1 = m2; /* Store the prev median */
m2 = ar2[j];
j++;
}
}

return (m1 + m2)/2;
}

/* Driver program to test above function */
int main()
{
int ar1[] = {1, 12, 15, 26, 38};
int ar2[] = {2, 13, 17, 30, 45};

printf("%d", getMedian(ar1, ar2, 5)) ;

getchar();
return 0;
}

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

3rd Algo O(logn)

This method works by first getting medians of the two sorted arrays and then comparing them.

Let ar1 and ar2 be the input arrays.

Algorithm:

1) Calculate the medians m1 and m2 of the input arrays ar1[]
and ar2[] respectively.
2) If m1 and m2 both are equal then we are done.
return m1 (or m2)
3) If m1 is greater than m2, then median is present in one
of the below two subarrays.
a) From first element of ar1 to m1 (ar1[0...|_n/2_|])
b) From m2 to last element of ar2 (ar2[|_n/2_|...n-1])
4) If m2 is greater than m1, then median is present in one
of the below two subarrays.
a) From m1 to last element of ar1 (ar1[|_n/2_|...n-1])
b) From first element of ar2 to m2 (ar2[0...|_n/2_|])
5) Repeat the above process until size of both the subarrays
becomes 2.
6) If size of the two arrays is 2 then use below formula to get
the median.
Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2

Example:

ar1[] = {1, 12, 15, 26, 38}
ar2[] = {2, 13, 17, 30, 45}

For above two arrays m1 = 15 and m2 = 17

For the above ar1[] and ar2[], m1 is smaller than m2. So median is present in one of the following two subarrays.

[15, 26, 38] and [2, 13, 17]

Let us repeat the process for above two subarrays:

m1 = 26 m2 = 13.

m1 is greater than m2. So the subarrays become

[15, 26] and [13, 17]
Now size is 2, so median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
= (max(15, 13) + min(26, 17))/2
= (15 + 17)/2
= 16




Complete Reference From http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf & geeksForgeeks

WAP to print 2D array matrix in Spiral Order

Question: Given a 2D array / matrix of integers. Write a program to print the elements in spiral order. Consider a matrix as show in the diagram to the right. The desired output of the program should be as: 1,2,3,4,8,12,16,20,19,18,17,13,9,5,6, 7,11,15,14,10.




Solution: There are several ways to solve this problem, but I am mentioning a method that is intuitive to understand and easy to implement. The idea is to consider the matrix similar to onion which can be peeled layer after layer. We can use the same approach to print the outer layer of the matrix and keep doing it recursively on a smaller matrix (with 1 less row and 1 less column).

Refer to the image below for a visual explanation. We start by printing the top-right layer of the matrix by calling the print_layer_top_right. It will print 1,2,3,4,8,12,16,20. The print_layer_top_right method then calls the print_layer_bottom_left method which will print 19,18,17,13,9,5. If you observe the size of the target matrix is reducing after each call. Each method basically calls the other method and passes the matrix indexes for the reduced matrix. Both methods take 4 index parameters which represent the target matrix. When the target matrix size is such that there is only one layer left the recursion terminates and by this time the code has printed all the numbers in the full matrix.




Code (C language):

<script type="syntaxhighlighter" class="brush: html"><![CDATA[

#include
void print_layer_top_right(int a[][4], int x1, int y1, int x2, int y2);
void print_layer_bottom_left(int a[][4], int x1, int y1, int x2, int y2);

int main(void)
{
int a[5][4] = {
{1,2,3,4},
{5,6,7,8},
{9,10,11,12},
{13,14,15,16},
{17,18,19,20}
};

print_layer_top_right(a,0,0,3,4);
}

//
// prints the top and right shells of the matrix
//
void print_layer_top_right(int a[][4], int x1, int y1, int x2, int y2)
{
int i = 0, j = 0;

// print the row
for(i = x1; i<=x2; i++)
{
printf("%d,", a[y1][i]);
}

//print the column
for(j = y1 + 1; j <= y2; j++)
{
printf("%d,", a[j][x2]);
}

// see if we have more cells left
if(x2-x1 > 0)
{
// 'recursively' call the function to print the bottom-left layer
print_layer_bottom_left(a, x1, y1 + 1, x2-1, y2);
}
}

//
// prints the bottom and left shells of the matrix
//
void print_layer_bottom_left(int a[][4], int x1, int y1, int x2, int y2)
{
int i = 0, j = 0;

//print the row of the matrix in reverse
for(i = x2; i>=x1; i--)
{
printf("%d,", a[y2][i]);
}

// print the last column of the matrix in reverse
for(j = y2 - 1; j >= y1; j--)
{
printf("%d,", a[j][x1]);
}

if(x2-x1 > 0)
{
// 'recursively' call the function to print the top-right layer
print_layer_top_right(a, x1+1, y1, x2, y2-1);
}
}

]]></script>

Run Here https://ideone.com/ut0Hx

WAP to Populate The next Higher in Singly Linked List

struct node
{
int data;
struct node *next;
struct node *next_larger;
}

initially next_larger of every node is point to NULL.
now write a c code which set all node's next_larger pointer.
where next_largest point to the next larger then its own value and largest value node's next_larger pointer points to NULL

i.e.
if LL is 3->1->5->6->4
then 3's next_larger points to 4
and 1's next_larger points to 3
and 5's next_larger points to 6
and 6's next_larger points to NULL
and 4's next_larger points to 5

#include
#include


struct node
{

int data;
struct node *next;
struct node *next_higher;

};

struct node* setNextHigher(struct node** head)
{
if(head==NULL)
return NULL;

struct node *start=*head;

(*head)=(*head)->next;

while((*head))
{

if((*head)->datadata)
{

(*head)->next_higher=start;
start= (*head);

}
else
{
struct node *p=start;
while(p->next_higher&&(*head)->data>=p->next_higher->data)
p=p->next_higher;

(*head)->next_higher=p->next_higher;
p->next_higher=(*head);

}
(*head)= (*head)->next;
}

return start;
}

void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */
new_node->next = (*head_ref);

/* move the head to point to the new node */
(*head_ref) = new_node;
}

/* Function to print linked list */
void printList(struct node *node)
{
while(node != NULL)
{
printf("%d ", node->data);
node = node->next_higher;
}
}

int main()
{
/* Start with the empty list */
struct node* head = NULL;

push(&head, 4);
push(&head, 6);
push(&head, 5);
push(&head, 1);
push(&head, 3);

head=setNextHigher(&head);

printList(head);

getchar();
}


Run Here https://ideone.com/fARV8

WAP to Implement The Counting Sort Pure O(n)

#include
#include

void counting_sort(int array[], int size)
{
int i, min, max;

min = max = array[0];
for(i = 1; i < size; i++)
{
if (array[i] < min)
min = array[i];
else if (array[i] > max)
max = array[i];
}

int range = max - min + 1;
int *count =(int*)malloc(range * sizeof(int));

for(i = 0; i < range; i++)
count[i] = 0;

for(i = 0; i < size; i++)
count[ array[i] - min ]++;
int j, z = 0;
for(i = min; i <= max; i++)
for(j = 0; j < count[ i - min ]; j++)
array[z++] = i;

free(count);
}

/* Explaination
// CountingSort.
//
// The data to be sorted is in array A with
// subscripts 0..n-1. For example,
//
// subscript: 0 1 2 3 4 5 6 7 8
// A = [ 2, 0, 4, 1, 4, 2, 2, 1, 0 ]
//
// The data values range from 0 to MAX (=4).
// A second array B will hold the sorted data.
//
// Initialize a "counting array" C:
// ---------------------------------------------

for (i = 0; i <= MAX; i++)
C[i] = 0;

// ---------------------------------------------
// Count how often each value occurs in A:
// ---------------------------------------------

for (i = 0; i < n; i++)
C[A[i]]++;

// ---------------------------------------------
// At this point C[i] contains the number
// of occurrences of the value i in A. In
// the example:
//
// 0 1 2 3 4
// C = [ 2, 2, 3, 0, 2 ]
//
// Make C[i] contain the number of
// occurrences of values 0..i in A:
// ---------------------------------------------

for (i = 1; i <= MAX; i++)
C[i] += C[i-1];

// ---------------------------------------------
// In the example:
//
// 0 1 2 3 4
// C = [ 2, 4, 7, 7, 9 ]
//
// Note that now C[i] is such that in the sorted
// array, the last occurrence of value i will be
// just before position C[i] (e.g., the last 2 in
// the sorted array B will be just before position
// C[2]=7).
//
// Move values from A to B, using C to know
// where to put them:
// ---------------------------------------------

for (i = n-1; i >= 0; i--)
B[--C[A[i]]] = A[i];

// ---------------------------------------------
// Now B looks like
//
// 0 1 2 3 4 5 6 7 8
// B = [ 0, 0, 1, 1, 2, 2, 2, 4, 4 ]
//
// Not that it matters, but now C[i] contains the
// subscript of the first occurrence of value i
// in the sorted array B:
//
// 0 1 2 3 4
// C = [ 0, 2, 4, 7, 7 ]
//
*/
void counting_sort_n(int A[],int n)
{

int i, min, MAX;

min = MAX= A[0];
for(i = 1; i < n; i++)
{
if (A[i] < min)
min = A[i];
else if (A[i] > MAX)
MAX= A[i];
}

int range = MAX- min + 1;
int *C =(int*)malloc(range * sizeof(int));
int *B=(int*)malloc(range * sizeof(int));
for (i = 0; i <= MAX; i++)
C[i] = 0;

for (i = 0; i < n; i++)
C[A[i]]++;

for (i = 1; i <= MAX; i++)
C[i] += C[i-1];

for (i = n-1; i >= 0; i--)
B[--C[A[i]]] = A[i];

for(i=0;i<9;i++)
printf( "%d ", B[i]);

}
int main()
{
int a[]={5,1,2,4,3};

//1st Method
counting_sort(a,5);

int i=0;
printf( "\n");
for(i=0;i<5;i++)
printf( "%d ", a[i]);

//2nd Method

int b[]={ 2, 0, 4, 1, 4, 2, 2, 1, 0};
counting_sort_n(b,9);



return 0;

}

Run here https://ideone.com/kLlEa

WAP Create a singly linked list of Leaf nodes from a binary tree

include

struct node
{
struct node *left, *right;
int data;

};


void LeafLinked(struct node *t, struct node **prevLeaf, struct node **head)
{
if(t)
{

if(t->left == NULL && t->right == NULL)
{ //leaf

if(*head == NULL)
*head = t;

else if(*prevLeaf)
(*prevLeaf)->next = t;

*prevLeaf = t;
}
else { //at least one child
LeafLinked(t->left, prevLeaf, head);
LeafLinked(t->right, prevLeaf, head);
}
}
}


/*Utilities*/

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);
}

inline void printList(struct node *t)
{
while(t)
{
printf("%d ", t->data);
t = t->next;
}
printf("\n");
}

int main()
{
/*level 0*/
struct node *t = newNode(10);

/*level 1*/
t->left = newNode(20);
t->right = newNode(30);


/*level 2*/
t->left->left = newNode(40);
t->left->right = newNode(70);
t->right->left = newNode(50);
t->right->right = newNode(60);

/*level 3*/
t->left->left->left = newNode(70);
t->right->right->left = newNode(60);
t->right->right->right = newNode(160);

/*Empty List head*/
struct node *head = NULL, *prevLeaf = NULL;

/*Convert tree to list*/
LeafLinked(t, &prevLeaf, &head);

/*print list*/
printList(head);


return 0;
}

Rune Here https://ideone.com/UOakN

Project Euler Problem 8- Finding product of 5 Consecutive in 1000 Digit Number

Source http://projecteuler.net/index.php?section=problems&id=8

public class Problem_8 {
public int getMaxProductOfFiveConsequtiveDigits(String[] nums) {
int maxProduct = 0;


for (String num : nums) {
int length = num.length();
if (length < 5)
continue;
int[] n = new int[5];
for (int i = 0; i < 5; i++)
n[i] = num.charAt(i) - '0';
int cycle = 5;
while (cycle < length) {
int prod = n[0] * n[1] * n[2] * n[3] * n[4];
if (prod > maxProduct)
maxProduct = prod;
n[cycle % 5] = num.charAt(cycle) - '0';
cycle++;
}
}

return maxProduct;
}

public static void main(String[] args) {
String[] nums = ("73167176531330624919225119674426574742355349194934"
+ "96983520312774506326239578318016984801869478851843"
+ "85861560789112949495459501737958331952853208805511"
+ "12540698747158523863050715693290963295227443043557"
+ "66896648950445244523161731856403098711121722383113"
+ "62229893423380308135336276614282806444486645238749"
+ "30358907296290491560440772390713810515859307960866"
+ "70172427121883998797908792274921901699720888093776"
+ "65727333001053367881220235421809751254540594752243"
+ "52584907711670556013604839586446706324415722155397"
+ "53697817977846174064955149290862569321978468622482"
+ "83972241375657056057490261407972968652414535100474"
+ "82166370484403199890008895243450658541227588666881"
+ "16427171479924442928230863465674813919123162824586"
+ "17866458359124566529476545682848912883142607690042"
+ "24219022671055626321111109370544217506941658960408"
+ "07198403850962455444362981230987879927244284909188"
+ "84580156166097919133875499200524063689912560717606"
+ "05886116467109405077541002256983155200055935729725"
+ "71636269561882670428252483600823257530420752963450").split("0");
System.out.println((new Problem_8()).getMaxProductOfFiveConsequtiveDigits(nums));
}
}


Run herer for Smaller Input https://ideone.com/SLY30