WAP to Implement Add,Subtract,Multiplication,Division Using Bit Manipulation

1st Approach to do the all operation

Addition

Here we use, One’s Complement Operator (~ - Known as Tilda). This is a Unary Operator. The output of “~b” means, One Complement of the value stored in ‘b’. For example, a=10, b=5. Then the ~b=-6. This operator simply works on the binary value of the corresponding Integer. As we know, One’s Complement is nothing but the Interchange of the 1’s and 0’s. So, If we give Input as b=5. The binary equivalent of 5 = 0000 0101 (Here we Consider that size of the Integer is 1 byte = 8 bits). Then the Complement of 5 = 1111 1010.Here the Most important thing is the Negative Numbers are stored in Computer as Two’s Complement Form. 2’s Complement = 1’s Complement + 1, And 1 111 1010, here the Left Most bit Represents the Sign of the Number, 1 indicates Negative, 0 Indicates Positive. So, Two’s Complement of 111 1010 is 000 0110 = 6, and of course, it is the Negative Number, so ~5 = -6. And Apply in the Expression, a-~b-1 = 10–(-6)-1 = 10+6–1 = 15. Simple Expression, But with Logic.

#include
#include

void main()
{
int a,b,sum;
clrscr();

printf("Enter 2 No.s : ");
scanf("%d%d",&a,&b); // Read 2 Integers

sum = a - ~b - 1; /* For the Explanation, See the Comments on Top */

printf("\nSum : %d",sum);
getch();
}

Subtraction
The Only difference here is the interchage of operators. Thats All.

For example, Assume that a=10, b=5. We know the difference is 5. Here we use the ‘~’ Operator in b. So ~b = – 6. Then a + ~b + 1 = 10 +(-6)+1 = 5. Simple Expression, But with Logic.

#include
#include

void main()
{
int a,b,sub;
clrscr();

printf("Enter 2 No.s : ");
scanf("%d%d",&a,&b); // Read 2 Integers

sub = a + ~b + 1; /* For the Explanation, See the Comments on Top */

printf("\nSubtraction : %d",sub);
getch();
}

Multiplication

This One is the Simply Logical. This will work all kind of Inputs. The concept behind this is We need to add the First Number, for Second Number Times. That’s All.

For example, Assume that a=5, b=4. We know the Answer is 20. Here we need to do is Adding the Number 5 itself,for 4 times. So We get the Answer as 20.

For better performance always add the Big Number,for Small Number Times. For Example to Multiply 5 * 100, better we Add 100,for 5 times, rather than adding 5, for 100 times.

#include
#include

void main()
{
int i,a,b,mul,big,small;
clrscr();

printf("Enter 2 No.s :\n");
scanf("%d%d",&a,&b); // Read 2 Numbers

if(a>b) // To find which is the Big one to Add Small one Times
{
big=a;
small=b;
}

else
{
big=b;
small=a;
}

mul=0; // Initialize the Variable to zero for Storing the Answer.

 for(i=1;i<=small;i++) // Adding Big Number, for Small Number Times. 
 {
     mul+=big; 
     printf("\n%d Times %d = %d",i,big,mul); 
 }
     printf("\n\nThe Answer is %d",mul); getch();
} 

 Division

This One is the Simply Logical. This will work all kind of Inputs. The concept behind this is We need to Perform the Reverse Operation performed on the Mutiplication Without '*' Opreator. Here we need to Subtract the Second Number From the First Number Until First Number >= Second Number. That’s All.

For example, Assume that a=10, b=3. Here we need to do is Subtract the Number 3 from the number 10 itself, until a>=b. And we should make a count for how many times we are doing like this, It is the Quotient Value.

So, finally We get the Answer as 3 Times we subtract 3 from the Number 10. Because we are checking the Condition a>=b everytime. So the is the Quotient as 3. The Remainder will be stored itself in 'a' as 1.

#include
#include

void main()
{
int a,b,c;
clrscr();

printf("Enter 2 No.s :\n");
scanf("%d%d",&a,&b); // Read 2 Numbers

if(b==0) // Here we are Checking for the Divide By Zero Error
{
printf("\nDivide By Zero Error");
}

else
{
c=0; // Here c as Count, and we should initialize the Count value to 0.
while(a>=b) // We Repeatedly Checking for the Condition a>=b
{
a = a - b; // Subtract b from a, and the new result stored in 'a' itself
c++; // Incrementing the Count
}

printf("\nQuotient = %d \n Remainder = %d",c,a); // Print Quotient and Remainder
}

getch();
}


Pure Low level Implementation (Bit Manipulation)

Lets Try For Decimal Integer Number how we add them

1 Add 759 + 674, but “forget” to carry I then get 323
2 Add 759 + 674 but only do the carrying, rather than the addition of each digit I then
get 1110
3 Add the result of the first two operations (recursively, using the same process de-
scribed in step 1 and 2): 1110 + 323 = 1433

we have done for decimal numbers

Now, how would we do this in binary?

1 If I add two binary numbers together but forget to carry, bit[i] will be 0 if bit[i] in a and
b are both 0 or both 1 This is an XOR
2 If I add two numbers together but only carry, I will have a 1 in bit[i] if bit[i-1] in a and b
are both 1’s This is an AND, shifted

3 Now, recurse until there’s nothing to carry

int add_no_arithm(int a, int b)
{
if (b == 0) return a;
int sum = a ^ b; // add without carrying
int carry = (a & b) << 1; // carry, but don’t add return add_no_arithm(sum, carry); // recurse 
 }

 Subtraction int sub(int x, int y)
{
      return(add(x,add(~y,1));

}

 Multiplication m=0;
 while (a)
 {
     if (a&1)
      m+=b; a>>=1;
     b<<=1; 
 }
printf("%d\n",m); The above code is a implementation of an algorithm better known as the Ethiopian 

Multiplication or the Russian Peasant Multiplication. Here’s the algorithm : 
 1. Let the two numbers to be multiplied be a and b. 
 2. If a is zero then break and print the result. 
 3. If a is odd then add b to the result. 
 4. Half a, Double b. Goto Step 2.

 Algorithm For Division :
 Given a dividend and a divisor would be to left shift (multiply by 2) the divisor till it reaches dividend/2, then continue this routine with the the difference between the dividend and divisor and divisor till the point where dividend is less than divisor or their difference is zero. This is similar to finding an element in a sorted list using the binary search algorithm, the C code is furnished below. #include

int dividend=17, divisor=2 , remainder;

int division(int tempdividend, int tempdivisor) 
{
int quotient = 1;

if (tempdivisor == tempdividend) {
remainder = 0;
return 1;
} else if (tempdividend < tempdivisor) { remainder = tempdividend; return 0; } while (tempdivisor <= tempdividend) { /* Here divisor < dividend, therefore left shift (multiply by 2) divisor and quotient */ tempdivisor = tempdivisor << 1; quotient = quotient << 1; } /* We have reached the point where divisor > dividend,
therefore divide divisor and quotient by two */
tempdivisor = tempdivisor >> 1;
quotient = quotient >> 1;

printf("\n %d %d", dividend, divisor);

/* Call division recursively for the difference to get the
exact quotient */
quotient = quotient + division(tempdividend - tempdivisor, divisor);

return quotient;
}

/* Division of two numbers without using division operator */
int main()
{
printf("\n%d / %d: quotient = %d", dividend, divisor, division(dividend, divisor));
printf("\n%d / %d: remainder = %d", dividend, divisor, remainder);

}

Run Here https://ideone.com/aSbGn

Source
http://www.prasannatech.net/2009/01/division-without-division-operator_24.html
http://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html

WAP to Remove Loop From Doubly Linked List Efficiently

Algorithm


This method is also dependent on Floyd’s Cycle detection algorithm.
1) Detect Loop using Floyd’s Cycle detection algo and get the pointer to a loop node.
2) Count the number of nodes in loop. Let the count be k.
3) Fix one pointer to the head and another to kth node from head.
4) Move both pointers at the same pace, they will meet at loop starting node.
5) Get pointer to the last node of loop and make next of it as NULL.

Note:One Test case Not Covered That I Will Do Later it Involve Prev Pointer




#include
#include

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

/* Function to remove loop. */
int removeLoop(struct node *, struct node *);

/* This function detects and removes loop in the list
If loop was there in the list then it returns 1,
otherwise returns 0 */
int detectAndRemoveLoop(struct node *list)
{
struct node *slow_p = list, *fast_p = list;

while (slow_p && fast_p && fast_p->next)
{
slow_p = slow_p->next;
fast_p = fast_p->next->next;

/* If slow_p and fast_p meet at some point then there
is a loop */
if (slow_p == fast_p)
{
removeLoop(slow_p, list);

/* Return 1 to indicate that loop is found */
return 1;
}
}

/* Return 0 to indeciate that ther is no loop*/
return 0;
}

/* Function to remove loop.
loop_node --> Pointer to one of the loop nodes
head --> Pointer to the start node of the linked list */
int removeLoop(struct node *loop_node, struct node *head)
{
struct node *ptr1 = loop_node;
struct node *ptr2 = loop_node;

// Count the number of nodes in loop
unsigned int k = 1, i;
while (ptr1->next != ptr2)
{
ptr1 = ptr1->next;
k++;
}

// Fix one pointer to head
ptr1 = head;

// And the other pointer to k nodes after head
ptr2 = head;
for(i = 0; i < k; i++)
ptr2 = ptr2->next;

/* Move both pointers at the same pace,
they will meet at loop starting node */
while(ptr2 != ptr1)
{
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}

// Get pointer to the last node
ptr2 = ptr2->next;
while(ptr2->next != ptr1)
ptr2 = ptr2->next;

/* Set the next node of the loop ending node
to fix the loop */
ptr2->next = NULL;
}

/* UTILITY FUNCTIONS */
/* Given a reference (pointer to pointer) to the head
of a list and an int, pushes a new node on the front
of the list. */
/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginging of the Doubly Linked List */
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;

/* since we are adding at the begining,
prev is always NULL */
new_node->prev = NULL;

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

/* change prev of head node to new node */
if((*head_ref) != NULL)
(*head_ref)->prev = new_node ;

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

/* Drier program to test above function*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;

push(&head, 10);
push(&head, 4);
push(&head, 15);
push(&head, 20);
push(&head, 50);

/* Create a loop for testing */
head->next->next->next->next->next = head->next->next;

detectAndRemoveLoop(head);

printf("Linked List after removing loop \n");
printList(head);

getchar();
return 0;
}

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

WAP to Detect Loop In Doubly Linked List

Algorithm : Floyd’s Cycle-Finding Algorithm:
This is the fastest method. Traverse linked list using two pointers.  Move one pointer by one and other pointer by two.  If these pointers meet at some node then there is a loop.  If pointers do not meet then linked list doesn’t have loop. Apart from above case one more cases may arises.

Case 1 : Whole link list is in loop. It Means last node points to first node. This can be solved by using two pointers. one pointer points to given node in link list and another pointers loops around the link list
If (Given_node == node->next) or or if(fast->prev=slow->prev)  Explained Above

Case 2: Part of link list is in loop
If (node->next != node->next->next->prev) is true means double link list is a loop.

 Time Complexity Will be O(N) N is length of Linked List




#include
#include

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

int detectLoop(struct node *list)
{
struct node *slow_p = list, *fast_p = list;

while(slow_p && fast_p &&
fast_p->next )
{
slow_p = slow_p->next;
fast_p = fast_p->next->next;
if (fast_p->prev==slow_p->prev|| slow_p == fast_p) //Look Closely !!!!!!!!!!!!!!!
{
printf("Found Loop");
return 1;
}

}
return 0;
}

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

new_node->data = new_data;

prev is always NULL */
new_node->prev = NULL;

new_node->next = (*head_ref);

if((*head_ref) != NULL)
(*head_ref)->prev = new_node ;

(*head_ref) = new_node;
}

void printList(struct node *node)
{
while(node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}

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

/* Let us create a sorted linked list to test the functions
Created linked list will be 10->8->4->2 */
push(&head, 2);
push(&head, 4);
push(&head, 8);
push(&head, 10);

printf("\n Original Doubly Linked list ");
printList(head);

//head->next->next->next=head->next; //1st test case
// head->next=head;//2nd test case //head->prev=head not necessary
head->next->next->prev=head;// 3rd Test Case
/* similarly we can do it using prev pointer for this we have to go to last node first the
start form its prev pointer .. so making the loop in program is our choice it depnds how we
connects them using prev & next pointer */

detectLoop(head);


//printf("\n After Looping Doubly Linked list ");
//printList(head); //Testing Purpose Only

getchar();
}

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

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