ansariinjnu
BAN USER/* is the following code correct for your problem ??? */
int findValue(int *value,int k)
{
int *p;
*p=value;
while(*(p+k-1))
{
if(*p==*(p+k))
return 1; //returning 1 for success
else
p++;
}
return -1;
}
To come up with (one of) the best possible solution to this problem, we need to be aware of the limitations and inherent advantages of using a BST. The problem can then be solved efficiently. Let us take a look at (some of) the properties of BST and the nature of the problem that’ll help us in finding a solution that is very close to the best possible solution.
1. In a BST, the numbers are sorted in a particular order during insertion. For any given node at any level, the value of the nodes in its left sub tree are always lesser than the value of the parent node and the value of the nodes in the right sub tree are always greater than the value of the parent node.
2. There are no nodes with duplicate values in a BST.
3. We have to eliminate (or don’t have to find) duplicate pairs.
Step 1. We first find (zero-in on) the node whose value is less than the given number n. We call this node newRoot (the logic behind this move is if we hope to find all pairs of numbers that add up to n in a BST, we should ignore the nodes that are greater or equal to n. Refer to point 1 above and this reasoning will seem obvious).
Step 2. Start with the node that was identified in step 1.
a. If the value of this node is less than n/2 then search for the node starting from newRoot with the value n – value (the logic is to limit the value for ki, our first number in the pair. If we find ki, kj must be out there).
b. If a node was found that satisfied the search condition in step 2a, print the pair [value, n – value] (we found kj using ki).
Step 3. Repeat step 2 for the current node’s left child.
Step 4. If the value of the current node is less than n/2, repeat step 2 for current node’s right child (there is no point looking for a number on the right side of the current node if the node’s value is greater than n/2 since we know we won’t find it).
public static int[] merge(int[] a, int[] b) {
int[] answer = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length)
{
if (a[i] < b[j])
{
answer[k] = a[i];
i++;
}
else
{
answer[k] = b[j];
j++;
}
k++;
}
while (i < a.length)
{
answer[k] = a[i];
i++;
k++;
}
while (j < b.length)
{
answer[k] = b[j];
j++;
k++;
}
return answer;
}
Given a singly linked list, write a function to swap elements pairwise. For example, if the linked list is 1->2->3->4->5 then the function should change it to 2->1->4->3->5, and if the linked list is 1->2->3->4->5->6 then the function should change it to 2->1->4->3->6->5.
METHOD 1 (Iterative)
Start from the head node and traverse the list. While traversing swap data of each node with its next node’s data.
/* Program to pairwise swap elements in a given linked list */
#include<stdio.h>
#include<stdlib.h>
/* A linked list node */
struct node
{
int data;
struct node *next;
};
/*Function to swap two integers at addresses a and b */
void swap(int *a, int *b);
/* Function to pairwise swap elements of a linked list */
void pairWiseSwap(struct node *head)
{
struct node *temp = head;
/* Traverse further only if there are at-least two nodes left */
while(temp != NULL && temp->next != NULL)
{
/* Swap data of node with its next node's data */
swap(&temp->data, &temp->next->data);
/* Move temp by 2 for the next pair */
temp = temp->next->next;
}
}
/* UTILITY FUNCTIONS */
/* Function to swap two integers */
void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
/* Function to add a node at the begining of 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;
/* 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 nodes in a given linked list */
void printList(struct node *node)
{
while(node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
/* Druver program to test above function */
int main()
{
struct node *start = NULL;
/* The constructed linked list is:
1->2->3->4->5 */
push(&start, 5);
push(&start, 4);
push(&start, 3);
push(&start, 2);
push(&start, 1);
printf("\n Linked list before calling pairWiseSwap() ");
printList(start);
pairWiseSwap(start);
printf("\n Linked list after calling pairWiseSwap() ");
printList(start);
getchar();
return 0;
}
Time complexity: O(n)
METHOD 2 (Recursive)
If there are 2 or more than 2 nodes in Linked List then swap the first two nodes and recursively call for rest of the list.
/* Recursive function to pairwise swap elements of a linked list */
void pairWiseSwap(struct node *head)
{
/* There must be at-least two nodes in the list */
if(head != NULL && head->next != NULL)
{
/* Swap the node's data with data of next node */
swap(&head->data, &head->next->data);
/* Call pairWiseSwap() for rest of the list */
pairWiseSwap(head->next->next);
}
}
Time complexity: O(n)
Please write comments if you find any bug in above code/algorithm, or find other ways to solve the same problem.
Step 1:store the first string in p,
Step 2: store the second string in s,
Step 3: create a array(occurrence[26]) and initialise it with zero,
Step 4:find occurrence of leters in first string ,second string and increase the corresponding index in occurrence[26] array corresponding the 1st string and same time decrease the occurrence[26] corresponding the 2nd string ,{if p[i]==b the p[i]-‘a’ will be 1}
Step 5 :If all the contents of occurrence[26] array is zero then both the string have same set of letter otherwise different letter .
Any problem cotact ansariinjnu@gmail.com
#include<stdio.h>
Int main()
{
Char p[10],s[10];
Int i=0,occurrence[26]={0};
Printf(“\nEnter the 1st string”);
Gets(p);
Printf(“\nEnter the 2nd string”);
Gets(s);
While(*p && *s)
{
Occurrence[p[i]-‘a’]++;
Occurrence[s[i++]-‘a’]--;
}
If(*p || *s)
{
Printf(“Both string is not same:”);
Return;
}
I=0;
While( i<26 && ! occurrence[i])
I++;
If(i==26)
Printf(“Bothe string is same”);
Else
Printf(“Bothe string is not same:”);
Retirn 0;
}
in for loop...float z= num/i;here 1st time i=0 and z=num/0 gives infinite...
- ansariinjnu June 13, 2013