Given a binary tree, find the largest Binary Search Tree (BST), where largest means BST with largest number of nodes in it. The largest BST may or not

Given a binary tree, find the largest Binary Search Tree (BST), where largest means BST with largest number of nodes in it. The largest BST may or may not include all of its descendants.


From now onwards, we use the term largest BST for largest BST which may or may not include all of its descendants, while largest BST subtree is for largest BST subtree which must include all of its descendants.

The example I showed in my last post was too trivial, so here I show a slightly more complicated example.

___________________15___________________
/ \
___________10___________ 20
/ \
5 _____7____
/ \
__2__ __5
/ \ /
0 8 3

The largest BST (may or may not include all of its descendants) from the above example should be:

____15____
/ \
_10 20
/
5

while the largest BST subtree (must include all of its descendants) should be:

__2_
/ \
0 8

An Incorrect Solution:

One might try to do an in-order traversal of the binary tree and find the longest increasing contiguous sequence or the longest increasing subsequence. Although these two approaches seemed to work for many cases, they are flawed and cannot handle the above case.

Let’s do an in-order traversal for the above binary tree:

5 10 0 2 8 7 3 5 15 20

The longest increasing contiguous sequence is:

3 5 15 20

The longest increasing subsequence is:

0 2 3 5 15 20

As you can see, neither one of them is correct.

A Top-down Approach:
The largest BST subtree solution requires a bottom-up approach where the min and max values are passed bottom-up. The main reason of doing this is when one of the nodes does not satisfy the BST properties, all subtrees above (which includes this node as well) must also not satisfy the BST requirements.

However, finding the largest BST requires a slightly different approach. We want the largest BST by including as many nodes as possible while we traverse down the tree, as long the current BST constraint is maintained. What happens when we see a node that breaks the current BST constraint? The answer is we can simply exclude it. However, we must treat it as an entirely new tree (ie, find in that tree if there is another larger BST). As you can see, we are passing the min and max values top-down, while the nodes count are passed bottom-up (Read my previous post to know how).

As a tree is defined recursively using its left and right subtrees, you could not simply return root node of the largest BST as this would include all of its subtrees. You would need to create copies of the subtrees or delete nodes from the original binary tree. My code below create copies of the subtrees. As it does not handle the deletion of trees, some of the subtrees that are created dynamically will eventually be memory-leaked. Handling this problem would require more complicated code. I will not demonstrate how to do it here since this post is to illustrate the algorithm.



// Find the largest BST in a binary tree.
// This code does not delete dynamically-allocated nodes,
// so memory will be leaked upon exit.
// The min and max values are passed top-down to check if
// including a node satisfies the current BST constraint.
// The child nodes are passed bottom-up to be assigned
// to its parent.
// Returns the total number of nodes the child holds.
int findLargestBST(BinaryTree *p, int min, int max, int &maxNodes,
BinaryTree *& largestBST, BinaryTree *& child) {
if (!p) return 0;
if (min < p->data && p->data < max) {
int leftNodes = findLargestBST(p->left, min, p->data, maxNodes, largestBST, child);
BinaryTree *leftChild = (leftNodes == 0) ? NULL : child;
int rightNodes = findLargestBST(p->right, p->data, max, maxNodes, largestBST, child);
BinaryTree *rightChild = (rightNodes == 0) ? NULL : child;
// create a copy of the current node and
// assign its left and right child.
BinaryTree *parent = new BinaryTree(p->data);
parent->left = leftChild;
parent->right = rightChild;
// pass the parent as the child to the above tree.
child = parent;
int totalNodes = leftNodes + rightNodes + 1;
if (totalNodes > maxNodes) {
maxNodes = totalNodes;
largestBST = parent;
}
return totalNodes;
} else {
// include this node breaks the BST constraint,
// so treat this node as an entirely new tree and
// check if a larger BST exist in this tree
findLargestBST(p, INT_MIN, INT_MAX, maxNodes, largestBST, child);
// must return 0 to exclude this node
return 0;
}
}

BinaryTree* findLargestBST(BinaryTree *root) {
BinaryTree *largestBST = NULL;
BinaryTree *child;
int maxNodes = INT_MIN;
findLargestBST(root, INT_MIN, INT_MAX, maxNodes, largestBST, child);
return largestBST;
}

Let f(k) = y where k is the y-th number in the increasing sequence of non-negative integers with the same number of ones in its binary representation

Let f(k) = y where k is the y-th number in the increasing sequence of non-negative integers with the same number of ones in its binary representation as y, e.g. f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 1, f(4) = 3,
f(5) = 2, f(6) = 3 and so on. Given k >= 0, compute f(k).

Clarifying the question.

n binary representation number of ones
0 0 0
1 1 1
2 10 1
3 11 2
4 100 1
5 101 2
6 110 2
7 111 3
8 1000 1
9 1001 2
10 1010 2

Now look at 4. It is the third number with exactly 1 one in the "number of ones" column. Hence f(4) = 3.
Likewise, 10 is the fifth number with exactly 2 ones. Hence f(10) = 5.



#include
#include

int C[100][100];

int nCr (int n, int r)
{
if (n < r) return 0;
if (r == 1) return n;
if (r == 0) return 1;
if (n == r) return 1;
if (C[n][r] != -1) return C[n][r];
return C[n][r] = nCr(n-1,r-1)+nCr(n-1,r);
}

main ()
{
memset(C,-1,sizeof(C));
int k;
scanf ("%d",&k);

int pos = 0, c = 0, sz = 0;
while (k)
{
if (k % 2 == 1)
{
c++;
pos += nCr(sz,c);
}
k >>= 1;
sz++;
}
printf("%d\n",pos+1);
}

WAP a Function to check if a singly linked list is palindrome

METHOD 1 (By reversing the list)

1. Get the middle of the linked list.
2. Reverse the second half of the linked list.
3. Compare the first half and second half.
4. Construct the original linked list by reversing the
second half again and attaching it back to the first half

Implementation:
?
/* Program to check if a linked list is palindrome */
#include
#include
#define bool int

/* Link list node */
struct node
{
char data;
struct node* next;
};

void reverse(struct node**);
bool compareLists(struct node*, struct node *);

/* Function to check if given linked list is
palindrome or not */
bool isPalindrome(struct node *head)
{
struct node *slow_ptr = head;
struct node *fast_ptr = head;
struct node *second_half;
struct node *prev_of_slow_ptr = head;
char res;

if(head!=NULL)
{
/* Get the middle of the list. Move slow_ptr by 1
and fast_ptrr by 2, slow_ptr will have the |_n/2_|th
node */
while((fast_ptr->next)!=NULL &&
(fast_ptr->next->next)!=NULL)
{
fast_ptr = fast_ptr->next->next;

/*We need previous of the slow_ptr for
linked lists with odd elements */
prev_of_slow_ptr = slow_ptr;
slow_ptr = slow_ptr->next;
}

/* Case where we have even no of elements */
if(fast_ptr->next != NULL)
{
second_half = slow_ptr->next;
reverse(&second_half);
slow_ptr->next = NULL;
res = compareLists(head, second_half);

/*construct the original list back*/
reverse(&second_half);
slow_ptr->next = second_half;
}

/* Case where we have odd no. of elements. Neither first
nor second list should have the middle element */
else
{
second_half = slow_ptr->next;
prev_of_slow_ptr->next = NULL;
reverse(&second_half);
res = compareLists(head, second_half);

/*construct the original list back*/
reverse(&second_half);
prev_of_slow_ptr->next = slow_ptr;
slow_ptr->next = second_half;
}

return res;
}
}

/* Function to reverse the linked list Note that this
function may change the head */
void reverse(struct node** head_ref)
{
struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}

/* Function to check if two input lists have same data*/
int compareLists(struct node* head1, struct node *head2)
{
struct node* temp1 = head1;
struct node* temp2 = head2;

while(temp1 && temp2)
{
if(temp1->data == temp2->data)
{
temp1 = temp1->next;
temp2 = temp2->next;
}
else return 0;
}

/* Both are empty reurn 1*/
if(temp1 == NULL && temp2 == NULL)
return 1;

/* Will reach here when one is NULL
and other is not */
return 0;
}

/* Push a node to linked list. Note that this function
changes the head */
void push(struct node** head_ref, char 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 pochar to the new node */
(*head_ref) = new_node;
}

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

push(&head, 'p');
push(&head, 'e');
push(&head, 'e');
push(&head, 'p');

/* p->e->e->p */
if(isPalindrome(head) == 1)
printf("Linked list is Palindrome");
else
printf("Linked list is not Palindrome");

getchar();
return 0;
}

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


METHOD 2 (Using Recursion)
Thanks to Sharad Chandra for suggesting this approach.

Use two pointers left and right. Move right and left using recursion and check for following in each recursive call.
1) Sub-list is palindrome.
2) Value at current left and right are matching.

If both above conditions are true then return true.
?
#define bool int
#include
#include

/* Link list node */
struct node
{
char data;
struct node* next;
};

bool isPalindrome(struct node **left, struct node *right)
{
/* stop recursion here */
if (!right)
return true;

/* If sub-list is not palindrome then no need to
check for current left and right, return false */
bool isp = isPalindrome(left, right->next);
if (isp == false)
return false;

/* Check values at current left and right */
bool isp1 = (right->data == (*left)->data);

/* Move left to next node */
*left = (*left)->next; /* save next pointer */

return isp1;
}

/* UTILITY FUNCTIONS */
/* Push a node to linked list. Note that this function
changes the head */
void push(struct node** head_ref, char 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 pochar to the new node */
(*head_ref) = new_node;
}

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

push(&head, 'r');
push(&head, 'a');
push(&head, 'd');
push(&head, 'a');
push(&head, 'r');

/* r->a->d->a->r*/
if(isPalindrome(&head, head) == 1)
printf("Linked list is Palindrome");
else
printf("Linked list is not Palindrome");

getchar();
return 0;
}

Time Complexity: O(n)
Auxiliary Space: O(n) if Function Call Stack size is considered, otherwise O(1).

A Special Binary Tree is given, Where all leaf are marked with L and others are marked with N. every node can have 0 or at most 2 nodes.

Problems: Given a preorder traversal of tree as a string 'NNLLNLL' Non-leaf nodes are labelled N and Leaf ndoes are labelled L. Each node has either 0 or 2 children. Construct the tree given the preorder traversal string.

Explanation & Approaches

As we should see how pre-order traversal is arranged. Pre-order traversal means first put root node, then pre order traversal of left subtree and then pre order traversal of right subtree. As shown in below figure:

In normal scenario, it’s not possible to detect where left subtree ends and right subtree starts using only pre-order traversal. But here, we are given a special property. Since every node has either 2 children or no child, we can surely say that if a node exists then its sibling also exists. So every time we are computing a subtree, we need to compute its sibling subtree as well.

Secondly, whenever we get ‘L’ in the input string, that is a leaf so we can stop for a particular subtree at that point. So after this ‘L’ node (left child of its parent ‘L’), it’s sibling starts. If ‘L’ node is right child of its parent, then we need to go up in the hierarchy to find next subtree to compute.

Keeping above invariant in mind, we can easily determine, when a subtree ends and next start. It means that we can give any start node to our method and it can easily complete the subtree it generates w/o going outside its nodes.

We just need to take care, that we are passing correct start nodes to different subtrees.

Data Structure Used: Array & Binary Tree

Algorithm:
1.Check if Array is NULL or Not if yes return NULL //base Condition
2.if Array is Not Null then create node one by one element start from 0th index to n-1 index in
array .
3. Check if array value at ith index is L id yes then simply return that Node.
4 else increment i then call for left subtree
5 again increment i=i+1 call for right subtree

#include
using namespace std;

struct node
{
node *left;
char data;
node *right;

};


void insert(node **root, char d, int&);
void preorder(node *root);


int main()
{
node *root= NULL;


char a[] ={'N','N','N','L','L','L','L'};
//11 Test Cases Below How Much You More Wants
//{'N'};
//{'N','L','L'};
//{'N','N','L','L','N','L','L'};
//{'N','N','N','L','L','L','L'};
//{'N','L','N','L','N','L','L'};
//{'N','N','N','L','L','N','L','L'};
//{'N','L','N','N','L','L','N','L','L'};
//{'N','N','N','L','L','N','L','L','N','L','L'};
//{'N','N','L','L','N','N','L','L','N','L','L'};
//{'N','N','N','L','L','N','L','L','N','N','L','L','N','L','L'};
//{'L', 'N', 'L', 'L', 'L', 'N', 'N', 'N', 'L', 'N', 'L', 'L', 'N', 'N', 'L', 'N', 'N',};
int n = sizeof(a) / sizeof(char);

for(int i=0; idata = d;
(*root)->left = (*root)->right = NULL;
flag = 1;
return;
}
else
{
if((*root)->data == 'L')
return;
if((*root)->data == 'N')
{
insert(&(*root)->left, d, flag);
if(flag == 0)
insert(&(*root)->right, d, flag);
}
}
}

void preorder(node *root)
{
if(root == NULL)
return;


cout << root->data << " "; preorder(root->left);
preorder(root->right);
}


Time Complexity O(n)
Space Complexity O(1) if Stack Space is Not Considered else O(n)
Run Here https://ideone.com/O4m6n

Above Code Can be Made More Clear & Optimize by removing
tree* construct_tree(char* A, int *i)
{
//Boundary Condition
if (A == NULL)
{
return NULL;
}

tree *node = newnode(A[*i]);
//On reaching leaf node, return
if (A[*i] == 'L'){
return node;
}

//Populate left sub tree
*i = *i + 1;
node->left = construct_tree(A, i);

//Populate right sub tree
*i = *i + 1;
node->right = construct_tree(A, i);

return node;
}

Run Here https://ideone.com/gYTWC

Java Program Using Parent Node



import java.io.Console;

public class Node{
public Node parent;
public Node left;
public Node right;
public char label;

public Node(Node parent,Node left, Node rigth, char label){
this.parent = parent;
this.left = left;
this.right = right;
this.label = label;
}

public static void main(String[] args){
Console console = System.console();
String preorder = console.readLine("Enter the preorder traversal string:");
Node root = null;
Node current = null;

for(int i = 0; i if(preorder.charAt(i)=='N'){
if(root==null){
root = new Node(null,null,null,'N');
current = root;
} else {
if(current.left==null){
Node temp = new Node(current,null,null,'N');
current.left = temp;
current = temp;
} else if(current.right==null){
Node temp = new Node(current,null,null,'N');
current.right=temp;
current = temp;
}
}
} else {
if(root==null){
root = new Node(null,null,null,'L');
current = root;
break;
} else {
if(current.left==null){
Node temp = new Node(current,null, null, 'L');
current.left = temp;
} else if(current.right==null){
Node temp = new Node(current, null,null,'L');
current.right=temp;
while(current!=null && current.right!=null){
current = current.parent;
}
}
}
}
}
System.out.println("==== Preorder traversal of tree constructed ======");
inorderTraversal(root);
System.out.println();
System.out.println("==================================================");
}

public static void inorderTraversal(Node root){
if(root!=null){
System.out.print(root.label);
inorderTraversal(root.left);
inorderTraversal(root.right);
}
}
}

Time Complexity O(N)
Space Complexity O(1)
Run Here http://ideone.com/T4fhM

Get Level of a node in a Binary Tree February 27, 2011 Given a Binary Tree and a key, write a function that returns level of the key.

#include

/* A tree node structure */
struct node
{
int data;
struct node *left;
struct node *right;
};

/*
Helper function for getLevel(). It returns level of the data if data is
present in tree, otherwise returns 0.
*/
int getLevelUtil(struct node *node, int data, int level)
{
if ( node == NULL )
return 0;

if ( node->data == data )
return level;

return getLevelUtil ( node->left, data, level+1) |
getLevelUtil ( node->right, data, level+1);
}

/* Returns level of given data value */
int getLevel(struct node *node, int data)
{
return getLevelUtil(node,data,1);
}

/* Utility function to create a new Binary Tree node */
struct node* newNode(int data)
{
struct node *temp = new struct node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;

return temp;
}

/* Driver function to test above functions */
int main()
{
struct node *root = new struct node;
int x;

/* Constructing tree given in the above figure */
root = newNode(3);
root->left = newNode(2);
root->right = newNode(5);
root->left->left = newNode(1);
root->left->right = newNode(4);

x = 3;
printf(" Level of %d is %d", x, getLevel(root, x));

x = 6;
printf(" Level of %d is %d", x, getLevel(root, x));

getchar();
return 0;
}

Output:
Level of 3 is 1
Level of 6 is 0

Time Complexity: O(n) where n is the number of nodes in the given Binary Tree.

Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Print all the keys of tree in range k1 to k2.

i.e. print all x such that k1<=x<=k2 and x is a key of given BST. Print all the keys in increasing order.

For example, if k1 = 10 and k2 = 22, then your function should print 12, 20 and 22.

Algorithm:
1) If value of root’s key is greater than k1, then recursively call in left subtree.
2) If value of root’s key is in range, then print the root’s key.
3) If value of root’s key is smaller than k2, then recursively call in right subtree.


#include

/* A tree node structure */
struct node
{
int data;
struct node *left;
struct node *right;
};

/* The functions prints all the keys which in the given range [k1..k2].
The function assumes than k1 < k2 */
void Print(struct node *root, int k1, int k2)
{
/* base case */
if ( NULL == root )
return;

/* Since the desired o/p is sorted, recurse for left subtree first
If root->data is greater than k1, then only we can get o/p keys
in left subtree */
if ( k1 < root->data )
Print(root->left, k1, k2);

/* if root's data lies in range, then prints root's data */
if ( k1 <= root->data && k2 >= root->data )
printf("%d ", root->data );

/* If root->data is smaller than k2, then only we can get o/p keys
in right subtree */
if ( k2 > root->data )
Print(root->right, k1, k2);
}

/* Utility function to create a new Binary Tree node */
struct node* newNode(int data)
{
struct node *temp = new struct node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;

return temp;
}

/* Driver function to test above functions */
int main()
{
struct node *root = new struct node;
int k1 = 10, k2 = 25;

/* Constructing tree given in the above figure */
root = newNode(20);
root->left = newNode(8);
root->right = newNode(22);
root->left->left = newNode(4);
root->left->right = newNode(12);

Print(root, k1, k2);

getchar();
return 0;
}

Output:
12 20 22

Time Complexity: O(k + Logn) where k is the number of keys in tree in the given range and n is the total number of keys in tree.

WAP fro Generica Swap & Simple Swp of two variable all possible method

Swapping two variables

Swapping two variables refers to mutually exchanging the values of two variables. For Example: If X & Y are two integer variable in C, such that

int X = 5;

int Y = 10;

Than after swapping X should be 10 and Y should be 5. Swapping can be done in variety of ways. We discuss few methods below

Method 1: Using Temporary variable
view sourceprint?
1 /* Let t be a temporary variable */
2 int t = X;
3 X = Y;
4 Y = t;

Above Algorithm looks very light & simple. It indeed is, if X & Y are integers.

What if, we are in C++ and X & Y are Objects of user defined class. Creating a temporary variable means constructor and Destructor will be called. Also there are two assignments (the first statement is initialization and not assignment), so Overloaded assignment operator will be called twice. This is a huge amount of task, especially when the Class is heavy.

What if the class has nested objects of another class, which are constructed in the Construction and destroyed in the destructor? Also to further complicate, let us consider the Class inheritance hierarchy, So Constructors of all the Base classes will be called.

But this method may be the only way to swap two objects in many cases.

So, as Himesh Reshammiya says “It’s complicated” !

Method 2: Using XOR operator.


view sourceprint?
1 // Swaping using XOR
2 X = X ^ Y;
3 Y = X ^ Y;
4 X = X ^ Y;

This method does not use the temporary object and use bit-wise operator which is believed to be more compact than other operators (Compiler dependent).

The disadvantage of this method is that it can only be applied to low-level data types like integers & characters (char, short, int, long). C & C++ does not allow bit-wise operation on non-integral operands.

A Major flaw in this algo is that it won’t work if X & Y uses same memory location. The contents of that location will be Zero when the first statement is executed.

view sourceprint?
1 void swap(int *x, int * y){
2 // this check is compulsory, else it may not work properly for cases
3 // where x & y points to the same memory location.
4 if(x != y)
5 x ^= y ^= x ^=y;
6 }

Same Problem will occur if x & y are references to the same memory location.

Method 3: Using +,- operator.
view sourceprint?
1 X = X + Y;
2 Y = X - Y;
3 X = X - Y;

this method can however, only be applied on numeric values.

If we have addition and subtraction overloaded for a user defined type and we accidently try to swap using the above code, then we may run into bigger problems, because the compiler will not complain and the result may not be what we expect it to be.

The issue of arithmetic overflow is also there. For Example: Consider a hypothetical environment where the maximum limit of integers is 100, and we want to swap X & Y with values 40 & 70 respectively. Swapping them using temporary variable (Method 1) or XOR (Method 2) will be correct but in this case the result will be undefined because 40 + 70 = 110 will result in an integer value overflow.

Note: In most of the environments, integers are stored in 2′s complement notation. If we perform above addition and subtraction in 2′s complement notions, then the result will be correct. But that is only because of the cyclic nature of 2′s complement representation and it is not guaranteed by the language.

Method 4: Using *, / operators

The above (Method 3) can be used with multiplication & divide operators in place of +, – operators.

Method 5: Swapping Pointers

Swapping pointers pointing to two different memory locations is very different from swapping the contents of those memory locations, though the results, in some cases, may be similar (not same).

For Example: If you want to swap two variables on heap and only one pointer points to each memory location, swapping the pointers will look similar to swapping the contents of the two memory locations.

Let ptr1 & ptr2 are two integer pointers pointing to memory locations containing 50 & 70 respectively,

then after swapping ptr1 and ptr2 will result in the below memory snap-shot:

Please note that if there is a third pointer ptr3 which also points to memory containing 50, then value-at ptr3 (*ptr3) will not change. But if we swap the contents of memory locations then *ptr3 will also be 70.

Either swapping of pointers or swapping the actual contents of the memory should be done depends on the requirements.

Since pointer variables are of fixed size and are non-negative integers, the XOR method of swapping can be used to swap two pointers.

If we swap the contents and not the pointers then we may end up using method 1 (particularly if we are dealing with user defined classes). And as discussed above it will have the complications of object creation, destruction & assignment operator calling.

Method 6: Generic Swapping

Using generic pointers or Macros in C language (void*) or templates in C++, we can define a generic swap function, which can swap two variable of any given datatype. (The macros may be error prone, though):

Generic pointers
view sourceprint?
1 void swap(void *vp1, void *vp2, int size)
2 {
3 char buffer[large]; // Large is a constant
4 memcpy(buffer,vp1,size);
5 memcpy(vp1,vp2,size);
6 memcpy(vp2,buffer,size);
7 }

Macro
view sourceprint?
1 #define SWAP(x, y, data_type) {data_type t=x; x=y; y=t; }

But the above macro does not work for all types and is more error prone than the other two variations.

Templates
view sourceprint?
1 template void swap(T&a, T &b)
2 {
3 T temp;
4
5 temp = a;
6 a = b;
7 b = temp;
8 }

In the above case the variables are passed by reference so that the actual arguments will get swapped. By default the values are passed by values and hence will swap the local variables of a function. To call the above template function for integers ,

swap(a,b);

WAP to Count no. of zeros before 1 has arrived in a Number

#include

int main ()
{
int ch=12;
int i;
int count=0;

for(i=32;i>=0;i--)
{
if((ch & 1)==0)
{
count++;
ch=ch>>1;
}
else
break;
}
printf("%d\n",count);
return 0;
}

Wap to Find Min. Distance Between Two Character

#include
#include

#define min(a,b) (a) < (b) ? (a) : (b)

int mindist(const char *s, const char a, const char b)
{
if(!s || !*s)
return INT_MAX;

char lastchar = '\0',
c;

int lastpos,
i = 0,
m = INT_MAX;

while((c = s[i]))
{
if((c == a) || (c == b))
{

if((c == a && lastchar == b) || (c == b && lastchar == a))
{
m = min(m, i - lastpos);
}
lastchar = c;
lastpos = i;
}
i++;
}
return m;
}

int main()
{
char *s="shashank";
char a='s';
char b='k';

int d;

if((d = mindist(s, a, b)) != INT_MAX)
{
printf("%d\n", d);
}
}

Ans. 4

Given Arrays as If [a1,a2,a3...,an,b1,b2...bn] is given input change this to [a1,b1,a2,b2.....an,bn]

#include

void print_arr(int* arr, int len)
{
int i;
printf("\n Array is \n");
for (i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
printf("\n");

}

int get_right_index(int i, int len)
{
if (i < len/2) {
return 2*i;
}
return 2*(i-len/2)+1;

}

int get_right_candidate(int i, int len)
{
if (i%2) {
return (i-1)/2 + len/2;
}
return i/2;

}

void make_pattern(int* arr, int len)
{
if (len%2) {
return;
}

if (len == 2)
{
return;
}

int total_no_assign = 0;
int index = 1;

while (total_no_assign < (len -2)) {
int cur = index;
int val = arr[cur];
int target_index = get_right_index(cur, len);

if (val < 0) {
printf("\n Already shuffled");
index++;
continue;
}

while(cur != target_index) {
int ci = get_right_candidate(cur, len);
arr[cur] = 0 - arr[ci];
printf("\n Index shuffled cur = %d, ci = %d\n", cur, ci);
cur = ci;
total_no_assign++;
print_arr(arr, len);
}

arr[cur] = 0 - val;
total_no_assign++;
print_arr(arr, len);
}

int i;
for (i = 0; i < len; i++) {
if (arr[i] < 0) {
arr[i] = 0 - arr[i];
}
}

}

int main()
{
int arr[]={1,2,3,4,5,6,7,8};

int count=sizeof(arr)/sizeof(int);
if (count%2) {
return -1;
}




print_arr(arr, count);

make_pattern(arr, count);
print_arr(arr, count);

return 0;

}