WAP to Construct Fully Binary Tree From Given Number of Nodes. Efficiently

Given a number of nodes N of a binary tree , how many structurally different full binary trees are possible.
A binary tree is said to be full binary tree , if for every node in the tree there exists exactly zero or 2 children.

Example: When N = 5 , No. of possible trees = 2

{{{

o o
/ \ / \
o o o o
/ \ / \
o o o o

}}}


The idea behind this deduction is that successive applications of a binary operator can be represented in terms of a full binary tree.If there are n binary operators then there will be n+1 operands and total number of representations (which will be full binary trees) will be equal to Catalan number for 'n'.
e.g. if we take nodes as a,b,c and +,+. Then total number of nodes is 5 and total number of binary operator is 2 so total number of structurally different full binary trees is 2.
So if we simulate in the same way that how many structurally different full binary trees can be created for a given N (total number of nodes) we can observe that
N = n (number of operator) + (n+1) (number of operands)
so n = (N-1)/2
Now get the corresponding Catalan number for n, which is the answer to this question.

#include

int fact(unsigned int n)
{
if (n <= 1)k
return 1;
else
return n * fact(n-1);
}

int fully_bst(int n) //n= N-1/2
{

if(n==0||n==1)
return 1;
else return ((fact(2*n))/(fact(n+1)*fact(n)));
}

int main()
{

printf("%d ",fully_bst(2));

return 0;
}

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

WAP to Check Given Binary Tree Can Have Mirror Image e.g we have to Check wheather This Tree Can Be Foldable or Not

A tree can be folded if left and right subtrees of the tree are structure wise mirror image of each other. An empty tree is considered as foldable.

Consider the below trees:
(a) can be folded.
(d) cannot be folded.


a)
10
/ \
7 15
\ /
9 11


(c)
b
/ \
f e
/ /
a q

(d)

a
/ \
b c
/ \ /
e f d


Algorithm

IsFold(root)
1) If tree is empty then return true
2) Else check if left and right subtrees are structure wise mirrors of
each other. Use utility function IsFoldable(root->left,
root->right) for this.

// Checks if n1 and n2 are mirror of each other.

IsFoldable(n1, n2)
1) If both trees are empty then return true.
2) If one of them is empty and other is not then return false.
3) Return true if following conditions are met
a) n1->left is mirror of n2->right
b) n1->right is mirror of n2->left


#include
#include

/* You would want to remove below 3 lines if your compiler
supports bool, true and false */
#define bool int
#define true 1
#define false 0

/* 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;
};

/* A utility function that checks if trees with roots as n1 and n2
are mirror of each other */
bool IsFoldable(struct node *n1, struct node *n2);

/* Returns true if the given tree can be folded */
bool IsFold(struct node *root)
{
if (root == NULL)
{ return true; }

return IsFoldable(root->left, root->right);
}

/* A utility function that checks if trees with roots as n1 and n2
are mirror of each other */
bool IsFoldable(struct node *n1, struct node *n2)
{
/* If both left and right subtrees are NULL,
then return true */
if (n1 == NULL && n2 == NULL)
{ return true; }

/* If one of the trees is NULL and other is not,
then return false */
if (n1 == NULL || n2 == NULL)
{ return false; }

/* Otherwise check if left and right subtrees are mirrors of
their counterparts */
return IsFoldable(n1->left, n2->right) &&
IsFoldable(n1->right, n2->left);
}

/*UTILITY FUNCTIONS */
/* 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);
}

/* Driver program to test mirror() */
int main(void)
{
/* The constructed binary tree is
1
/ \
2 3
\ /
4 5
*/
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->right = newNode(4);
root->right->left = newNode(5);

if(IsFold(root) == true)
{ printf("\n tree is foldable"); }
else
{ printf("\n tree is not foldable"); }

getchar();
return 0;
}

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

WAP Convert Given Binary Tree into its Mirror Tree Efficiently

This Problem Can Be Solved Using Two Approach

1.Top Down
2 Bottom Up


1.Top Down
Start from The Root create copy of it & then create copy for left & right sub tree by calling copy function recursively


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

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

/* Change a tree so that the roles of the left and
right pointers are swapped at every node.

So the tree...
4
/ \
2 5
/ \
1 3

is changed to...
4
/ \
5 2
/ \
3 1
*/
struct node* copy(struct node *root)
{
struct node *temp;

if(root==NULL)
return(NULL);
temp = (struct node*) malloc(sizeof(struct node));
temp->data= root->data;

temp->left = copy(root->right);
temp->right = copy(root->left);

return(temp);
}

/* Helper function to test mirror(). Given a binary
search tree, print out its data elements in
increasing sorted order.*/
void inOrder(struct node* node)
{
if (node == NULL)
return;

inOrder(node->left);
printf("%d ", node->data);

inOrder(node->right);
}

/* Driver program to test mirror() */
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->left->left->left = newNode(6);
root->left->right->right = newNode(7);
/* Print inorder traversal of the input tree */
printf("\n Inorder traversal of the constructed tree is \n");
inOrder(root);

/* Convert tree to its mirror */
root=copy(root);

/* Print inorder traversal of the mirror tree */
printf("\n Inorder traversal of the mirror tree is \n");
inOrder(root);

getchar();
return 0;
}

Time Complexity O(n)
Space Complexity O(1) if stack space not considered else O(n)
Run Here https://ideone.com/QnMjQ


Bottom Up Approach ..First create mirror tree for left & right sub tree them comes to root


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

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

/* Change a tree so that the roles of the left and
right pointers are swapped at every node.

So the tree...
4
/ \
2 5
/ \
1 3

is changed to...
4
/ \
5 2
/ \
3 1
*/
void copy(struct node* node)
{
if (node==NULL)
return;
else
{
struct node* temp;

/* do the subtrees */
copy(node->left);
copy(node->right);

/* swap the pointers in this node */
temp = node->left;
node->left = node->right;
node->right = temp;
}
}

/* Helper function to test mirror(). Given a binary
search tree, print out its data elements in
increasing sorted order.*/
void inOrder(struct node* node)
{
if (node == NULL)
return;

inOrder(node->left);
printf("%d ", node->data);

inOrder(node->right);
}

/* Driver program to test mirror() */
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);

/* Print inorder traversal of the input tree */
printf("\n Inorder traversal of the constructed tree is \n");
inOrder(root);

/* Convert tree to its mirror */
copy(root);

/* Print inorder traversal of the mirror tree */
printf("\n Inorder traversal of the mirror tree is \n");
inOrder(root);

getchar();
return 0;
}


Time Complexity O(n)
Space Complexity O(1) if stack space not considered else O(n)
Run Here https://ideone.com/emkO7

WAP to find minimum difference between elements of N sorted list of K size each Efficiently..I have done it O(n)

Given an N arrays of size K each.. each of these K elements in the N arrays are sorted, each of these N*K elements are unique. Choose a single element from each of the N arrays, from the chosen subset of N elements. Subtract the minimum and maximum element. Now, this
difference should be least possible Minimum.. Hope the problem is clear :) :)

Sample:

N=3, K=3

N=1 : 6, 16, 67
N=2 : 11,17,68
N=3 : 10, 15, 100

here if 16, 17, 15 are chosen.. we get the minimum difference as
17-15=2.


its very simple question but i saw lot people stuck to solve & approach in this.. i solved it

#include
#include
#include

int min_num(int a,int b ,int c)
{
int m=a;
if(m>b)
m=b;
if(m>c)
m=c;
return m;

}

int max_num(int a,int b,int c)
{
int m=a;
if(m m=b;
if(m m=c;
return m;
}

int minDist(int a[],int b[],int c[], int n)
{

int i = 0,
j = 0, k=0,
min=INT_MAX,
max=INT_MIN,
mins=INT_MAX,
cur;

while(i < n && j < n && k {
max=max_num(a[i],b[j],c[k]);
min=min_num(a[i],b[j],c[k]);

if(min==a[i])
i++;
else if(min==b[j])
j++;
else
k++;



cur = abs(max-min);

mins = mins < cur ? mins : cur;


}

return mins;
}

int main()
{

int a[]={6, 16, 67};
int b[]={11,17,68};
int c[]={ 10, 15, 100};
printf("%d\n", minDist(a,b,c,sizeof(a)/sizeof(int)));//all have equal size

return 0;
}


TC O(n)
Run here https://ideone.com/qq4ZN

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 Find Occurance of a Number N in Sorted Array in O(logn)

Given a sorted array and a number n.How can u find the number of occurance of n in the array . should be o(logn)


Modified Binary Search Algorithm

mid=low+high/2;
if(a[mid]>num)
search in right side & set low=mid+1 & return ;
else if(a[mid]search in left side of mid set high=mid-1 & return ;
else //its important instead of just of printing the num or incrementing the counter //i tried if you will do like this then it will be O(n) not O(logn) , si i will add 1 to recursively call for left side + recursively call for right side so every time this line executes we are incrementing the counter &
return 1+left_binsearch()+right_binsearch thus it will be in O(logn)


you people can dry run for this 1 2 2 3 3 3 4 4 4 low=0 high=8 mid=4 & run it



#include


int CountFreq (int *A, int value, int low, int high)
{
int mid;
if (high < low)
return 0;
mid = low + (high - low);
if (A[mid] > value)
return CountFreq (A, value, low, mid - 1);
else if (A[mid] < value)
return CountFreq (A, value, mid + 1, high);
else
return 1 + CountFreq (A, value, low, mid - 1) + CountFreq (A, value, mid + 1, high);
}

int main() {

int A[] = { 1,2,2,2,2,3, 3, 3,4,4,4, 4};
int value = 2;



printf("%d\n", CountFreq(A, value, 0, sizeof(A)/sizeof(int)-1));

return 0;

}

TC O(n) consider ar[]={3,3,3,3,3,3}, & x=3 T(n)=2*T(n/2)+c leads to O(n)
Sc O(1)
Run Here https://ideone.com/clone/mTGes


Method 2 Modified Binary Search

1) Use Binary search to get index of the first occurrence of x in arr[]. Let the index of the first occurrence be i.
2) Use Binary search to get index of the last occurrence of x in arr[]. Let the index of the last occurrence be j.
3) Return (j – i + 1);

why it works because we know that array i sorted so if find the first occurrence at position i & last occurrence at position j then we are sure that all the elements between i & j are the same value what they at ith & jth position it works because array is sorted & we have done ....Cheers

#include


/* if x is present in arr[] then returns the index of FIRST occurrence
of x in arr[0..n-1], otherwise returns -1 */
int first(int arr[], int low, int high, int x, int n)
{
if(high >= low)
{
int mid = (low + high)/2; /*low + (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;
}

/* if x is present in arr[] then returns the index of LAST occurrence
of x in arr[0..n-1], otherwise returns -1 */
int last(int arr[], int low, int high, int x, int n)
{
if(high >= low)
{
int mid = (low + high)/2; /*low + (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;
}


/* if x is present in arr[] then returns the count of occurrences of x,
otherwise returns -1. */
int count(int arr[], int x, int n)
{
int i; // index of first occurrence of x in arr[0..n-1]
int j; // index of last occurrence of x in arr[0..n-1]

/* get the index of first occurrence of x */
i = first(arr, 0, n-1, x, n);

/* If x doesn't exist in arr[] then return -1 */
if(i == -1)
return i;

/* Else get the index of last occurrence of x */
j = last(arr, 0, n-1, x, n);

/* return count */
return j-i+1;
}



/* driver program to test above functions */
int main()
{
int arr[] = {1, 2, 2, 2, 2, 3, 3};
int x = 2; // Element to be counted in arr[]
int n = sizeof(arr)/sizeof(arr[0]);
int c = count(arr, x, n);
printf(" %d occurs %d times ", x, c);
getchar();
return 0;
}

TC O(logn)
Sc O(1)
Run here https://ideone.com/J0enE

WAP to Find Square root of Perfect Square Number Efficiently Yes in O(logn)

As its a perfect square!! So arrange numbers from 1 to n/2 and do a binary search..
ie for i from 1 to n/2

Now compare mind*mid to n

if mid*midrecursively check right half
else
recursively check left half

#include

int sqrtof_perfect(int start,int end,int n)
{
if(start>end)
return 0;
while(start<=end)
{
int mid=(start+end)/2;
//int temp=mid*mid;
if(mid*mid==n)
return mid;
else if(mid*mid>n)
end=mid-1;
else
start=mid+1;

}
return -1;
}


int main()
{
int n=144;//9;//25; // so

printf("\n %d",sqrtof_perfect(1,n/2,n));
getchar();
return 0;
}


TC O(logn)
Sc O(1)

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