aka
BAN USERfind_out(node *root)
{
node *slow, *fast, *temp, *before_pointer;
/* find out the intersection point */
slow = root;
fast = slow->next->next;
while(slow != fast) {
slow = slow->next;
fast = fast->next->next;
}
/* ok now reset slow pointer to the start of node and
fast pointer is pointing to the intersection point */
temp = fast;
slow = root;
while(temp != slow) {
/* before_pointer is just before the intersection point
i.e. last node as referred to in the question */
before_pointer = temp;
temp = temp->next;
slow = slow->next;
}
printf("last data is %d\n", *before_pointer);
}
@gen-y-s: I think what you mean is this right?:
Suppose you have binary tree of this form:
8
6 11
5 7 10 12
We have postorder code as below which is slightly modified:
postorder(node)
if node == null then return
put_in_stack(node)
postorder(node.left)
postorder(node.right)
visit(node)
algorithm:
1.Start doing post order traversal.
2.put all the nodes in the stack as shown above i.e. basically all the paths from root to the current node.
3. Once you reach the node i.e. visit(node) in the above algorithm then just pop the node and do as below:
while(reach from bottom to top of stack) {
element = bottom_of_stack;
matrix[element][popped_node]=1.
bottom_of_stack++
}
code below:
#include<stdlib.h>
#include<stdio.h>
struct bin_tree {
int data;
struct bin_tree * right, * left;
};
typedef struct bin_tree node;
void insert(node ** tree, int val)
{
node *temp = NULL;
if(!(*tree))
{
temp = (node *)malloc(sizeof(node));
temp->left = temp->right = NULL;
temp->data = val;
*tree = temp;
return;
}
if(val < (*tree)->data)
{
insert(&(*tree)->left, val);
}
else if(val > (*tree)->data)
{
insert(&(*tree)->right, val);
}
}
void print_postorder(node * tree)
{
if (tree)
{
printf("stack %d\n", tree->data);
print_postorder(tree->left);
print_postorder(tree->right);
printf("%d\n",tree->data);
}
}
void main()
{
node *root;
node *tmp;
root = NULL;
/* Inserting nodes into tree */
insert(&root, 8);
insert(&root, 6);
insert(&root, 11);
insert(&root, 5);
insert(&root, 7);
insert(&root, 10);
insert(&root, 12);
printf("Post Order Display\n");
print_postorder(root);
}
dry run:
stack 8
stack 6
stack 5
5 {8,5} {6,5} ---> set the matrix and pop 5 from stack.
stack 7
7 {8,7} {6,7} ---> set the matrix and pop 7 from stack.
6 {8,6} ---> set the matrix and pop 6 from stack.
stack 11
stack 10
10 {8,10} {11,10} ---> set the matrix and pop 10 from stack.
stack 12
12 {8,12} {11,12} ---> set the matrix and pop 12 from stack.
11 {8,11} ---> set the matrix and pop 11 from stack.
8 --->pop it off :)
subset sum problem
int total=0;
#define SIZE(a) sizeof(a)/sizeof(a[0])
int arr[] = {1, 2, 3, 4};
int counter = 0;
void IsSubArray(int n, int N, int sum) // N is the number of elements in the array
{
if(sum == N) {
total++;
return;
}
if((n <= (SIZE(arr)-1)) && arr[n]+sum <= N) {
IsSubArray(n+1, N, sum+arr[n]);
}
if((n <= (SIZE(arr)-1)) && arr[n+1]+sum <= N) {
IsSubArray(n+1, N, sum);
}
}
int main()
{
int j, i;
int target_sum=3;
IsSubArray(0, target_sum, 0);
printf("%d\n", total);
return 0;
}
Modified subset sum problem and it works here as well.
int total=0;
#define SIZE(a) sizeof(a)/sizeof(a[0])
int arr[] = {2, 11, 20, 30, 31};
int counter = 0;
void IsSubArray(int n, int N, int sum) // N is the number of elements in the array
{
counter++;
if(sum == N) {
if(((counter%2) == 1)) {
printf("got it\n");
counter--;
}
return;
}
if((n <= (SIZE(arr)-1)) && arr[n]+sum <= N) {
IsSubArray(n+1, N, sum+arr[n]);
}
if((n <= (SIZE(arr)-1)) && arr[n+1]+sum <= N) {
counter--;
IsSubArray(n+1, N, sum);
}
}
int main()
{
int j, i;
int target_sum=51;
IsSubArray(0, target_sum, 0);
return 0;
}
@dadakhalandhar:
Sorry but did you actually read the question.I was lead to believe that you need to pass an argument to insert() which can take all the the mentioned data types.
insert(void *arg)
{
//you don't know here the type of argument
//so you can typecast it to any type and this
//typecasting can lead to data abort or undesired result
//unless you know beforhand what should i typecast it to??
}
downvoting it.
google for bit twiddling hacks.
int main()
{
int x = 0x000000F0;
x = ((x&0xAAAAAAAA) >> 1)| ((x& 0x55555555)<<1);
x = ((x&0xCCCCCCCC) >> 2)| ((x& 0x33333333)<<2);
x = ((x&0xF0F0F0F0) >> 4) | ((x& 0x0F0F0F0F)<<4);
x = ((x&0xFF00FF00) >> 8) | ((x& 0x00FF00FF)<<8);
x = x >> 16 | x<< 16;
printf("%x\n", x);
}
subset sum problem:don't know if it is right solution
int total=0;
#define SIZE(a) sizeof(a)/sizeof(a[0])
int arr[] = {1, 2, 3};
int visited[100];
void IsSubArray(int n, int N, int sum) // N is the number of elements in the array
{
visited[n] = 1;
if(sum == N) {
total++;
visited[n] = 0;
return;
}
if((n <= (SIZE(arr)-1)) && arr[n]+sum <= N) {
IsSubArray(n+1, N, sum+arr[n]);
}
if((n <= (SIZE(arr)-1)) && arr[n+1]+sum <= N) {
visited[n] = 0;
IsSubArray(n+1, N, sum);
}
}
int main()
{
int j, i;
int target_sum=3;
memset(visited, 0, sizeof(int)*100);
IsSubArray(0, target_sum, 0);
printf("total %d\n", total);
return 0;
}
int total=0;
#define SIZE(a) sizeof(a)/sizeof(a[0])
int arr[] = {1, 2, 3};
int visited[100];
void IsSubArray(int n, int N, int sum) // N is the number of elements in the array
{
visited[n] = 1;
if(sum == N) {
total++;
visited[n] = 0;
return;
}
if((n <= (SIZE(arr)-1)) && arr[n]+sum <= N) {
IsSubArray(n+1, N, sum+arr[n]);
}
if((n <= (SIZE(arr)-1)) && arr[n+1]+sum <= N) {
visited[n] = 0;
IsSubArray(n+1, N, sum);
}
}
int main()
{
int j, i;
int target_sum=3;
memset(visited, 0, sizeof(int)*100);
IsSubArray(0, target_sum, 0);
printf("total %d\n", total);
return 0;
}
solve using subset sum problem with one additional constraint, which is to find only two elements which add up to k.
Using binary tree example as explained in this paper.Very nice approach.
www dot wou.edu/~broegb/Cs345/SubsetSum.pdf
#define SIZE(a) sizeof(a)/sizeof(a[0])
int visited[100];
int a[] = {-5, -4, -1, 1, 4, 5};
int r[100];
int sum = 0;
void r_ss(int s, int k)
{
r[k] = 1;
if(s+a[k] == sum) {
int i, count=0;
// make ifdef 0 to print all the solutions
#if 1
for(i=0;i<SIZE(a);i++) {
if(r[i])
count++;
if(count > 2) {
r[k] = 0;
return;
}
}
#endif
for(i=0;i<SIZE(a);i++) {
if(r[i])
printf("found %d\n", a[i]);
}
r[k] = 0;
printf("got it\n");
return;
}
if((k+1<=SIZE(a)) &&((s+a[k]) <= sum))
r_ss(s+a[k], k+1);
if((k+1<=SIZE(a)) &&((s+a[k+1]) <= sum)) {
r[k] = 0;
r_ss(s, k+1);
}
}
int main()
{
memset(r, 0, sizeof(int)*100);
r_ss(0, 0);
return 0;
}
Based on the above algo.
#include <stdio.h>
int main()
{
int a[] = {1, 2, 3, 5, 6, 10, 11, 12};
int b[] = {2, 3, 3, 6, 9, 10, 11};
int c[100] = {0};
int size, i, j, l, k, m, p;
i = j = m = 0;
size = (sizeof(a)/sizeof(a[0])) > (sizeof(b)/sizeof(b[0]))?(sizeof(a)/sizeof(a[0])):(sizeof(b)/sizeof(b[0]));
memset(c, 0, sizeof(int)*100);
for(;;) {
if(a[i] > b[j]) {
j++;
} else if(a[i] < b[j]) {
i++;
} else if(a[i] == b[j]){
c[m++] = a[i];
i++;
}
if(i >= size || j >= size)
break;
}
for(i=0;i<m;i++)
printf("%d\n", c[i]);
return 0;
}
algo:
first list: 1 2 4 5 6
second list: 3 5 6 7 8 9
start from lowest of both the lists, in this case it is 1.
Have two variables for first list and second list.
var_first = 1
var_second = 3
output = min(var_first, var_second)
pick the second element from the list where output was found.In our case it is 2
var_first = 2
var_second = 3
keeps going....
var_first = 4
var_second = 3
var_first = 5
var_second = 5
whenever both variable are same put in the third list.
third list: 5 6
@DashDash: just extended your logic
#define SIZE 8
#define VISITED 567
int KnightMove(int (*a)[SIZE], int m, int n, int currx, int curry)
{
if(currx<0 || curry <0)
return 0;
if(currx >= SIZE || curry >= SIZE)
return;
//checking if 3,3 is reachable or not as we are starting
//from 0,0 index.
if(currx == 3 && curry == 3)
return 1;
if(a[currx][curry] == VISITED)
return 0;
else
{
a[currx][curry] = VISITED;
//move forward
if(KnightMove(a, m, n, currx-1, curry+2) == 1)
return 1;
if(KnightMove(a, m, n, currx+1, curry+2) == 1)
return 1;
//move sideways
if(KnightMove(a, m, n, currx-2, curry+1) == 1)
return 1;
if(KnightMove(a, m, n, currx-2, curry-1) == 1)
return 1;
if(KnightMove(a, m, n, currx+2, curry+1) == 1)
return 1;
if(KnightMove(a, m, n, currx+2, curry-1) == 1)
return 1;
a[currx][curry] = 0;
}
}
void printSolution(int sol[SIZE][SIZE])
{
int i, j;
for (i = 0; i < SIZE; i++)
{
for (j = 0; j < SIZE; j++)
printf("%8d", sol[i][j]);
printf("\n");
}
}
int main()
{
int a[SIZE][SIZE] = {0};
memset(a, 0, sizeof(int)*SIZE*SIZE);
KnightMove(a, SIZE, SIZE, 0, 0);
printSolution(a);
return 0;
}
It is always better to explain using dryruns:
{20,19,18,17,16,16,16,30,17,25,20};
a. start traversing from 0 to rightmost index and put the minimum found til now in stack.So we put numbers in the stack as below:
topmost bottomost
16 16 16 16 16 16 16 17 18 19 20
so 16 is the least.
b.Start traversing from rightmost to leftmost in the array and subtract the array element with topmost element of the stack at each step as below:
20 - 16 = 4
25 - 16 = 9
-
-
30-16 = 14
-
-
-
20 - 20 = 0
so greatest is 14 and we have the answer.
Upvoting this answer.
A B C D
3 3 3 1
weigh A and B: same ->1 weigh over
weigh B and C: same ->1 weigh over
D is probelmatic
maximum weighing 2.
Worst case:
weigh A and B: same ->1 weigh over
weigh B and C: not same ->1 weigh over
C is problematic so divide C as 1, 1 and 1.
Weigh 1 and 1 : same so third 1 is probelmatic : 3 weigh over
maximum weighing 3.
algo: subtract all the elements with next elements as shown below and once you get that then basically what we are looking for is a maximum subarray which can be find out using kadence algorithm.
//int a[] = {30, 12, 15, 10, 40, 30, 60, 100};
int a[] = {-18, 3, -5, 30, -10, 30, 40};
static int l_index = 0, h_index = 0;
int maximum_subarray(int* nums, int start_index, int end_index)
{
int max_sum = 0;
int cur_index, cur_sum = 0, max_ending_here, max_so_far;
for(cur_index = 0; cur_index < end_index; cur_index++) {
cur_sum = cur_sum + nums[cur_index];
if(cur_sum < 0) {
cur_sum = 0;
l_index = cur_index;
}
if(cur_sum > max_sum) {
max_sum = cur_sum;
h_index = cur_index;
}
}
return max_sum;
}
int main()
{
//int a[] = {30, 12, 15, 10, 40, 30, 60, 100};
int a[] = {-18, 3, -5, 30, -10, 30, 40};
printf("sum %d\n", maximum_subarray(a, 0, sizeof(a)/sizeof(a[0])));
printf("left %d right %d\n", l_index, h_index);
return 0;
}
containter 1 2 3
actually contatins : 'A' apple ,'O' orange ,'M' mixed
label shows : 'O' orange,'M' mixed, 'A' apple,
Remember that all labels are INCORRECT.
so if we pick any fruit from any basket we will be in a state as below:
we can pick from any container so let's pick from container 1.
pick from 1: 'A' apple
2 container can have either orange or mixed but as the label shows it is mixed it must be anything other than mixed(remember all labels are incorrect).We already know that 1 container has apple so we are left out with orange.So second container is orange and in the 3 container it will be mixed.
- aka June 01, 2013