rockstar
BAN USERwe just need to modify the inorder traversal.. thats it
call this function from main with calling as inordermodify(root);
void inordermodify(struct node *head)
{
static node *temp= NULL;
if(head != NULL)
{
inordermodify(head->right);
head->inordersucc = temp;
temp = head;
inordermodify(head->left);
}
}
we can do it through modified postorder traversal
int postorder(struct node *head,int sum)
{
if(head != NULL)
{
int s1= postorder(head->left,sum);
int s2= postorder(head->right,sum);
head->data = s1+s2+ head->data;
return(node->data);
}
return 0;
}
call(root,0) from main.. i hope i am clear in explaining
this is a simple c code.. O(n) solution.. people mite confuse if its O(n^2) but its O(n)
#include<stdio.h>
#include<conio.h>
void main()
{
int j;
int arr[10]={5,6,0,1,2,3,4,7,22,11};
int localstrt=0;int localend=0;
int longeststart=0;int longestend=0;
int i=0;
for(i=0;i<10;i++)
{
if(arr[i]<arr[i+1])
{
j=i;
localstrt=i;localend=i;
while((arr[j]<arr[j+1])&&(j<10))
{
j++;
}
localend=j;
if((longestend - longeststart)<(localend - localstrt))
{
longestend=localend;longeststart=localstrt;
}
i=j;
}
}
printf("%d %d",longeststart,longestend);
getch();
}
@anonymous.. dude question here is,is the tree binary.. there can be three struct node pointer in tree structure,where the third pointer always points to null(i knw its foolishness,but it is a valid argument).. if u look at the tree in that scenario.. still it will be a binary tree.. so structure on node alone doesn't determines its nature.
- rockstar September 11, 2012challenge accepted @ Code Ninja...
@eugene.yaravoi u might have undrstood the idea,if ny flaws,please let me know,bt O(n) is possible dude..
@anonymous.. nothing delusional have a luk at the code..might be some test cases nt fulfilled.. i will design new1 for those,if u can make ny..
her is O(n) code...
#include<stdio.h>
#include<math.h>
#include<conio.h>
int main()
{
int arr[10]={-1,2,-3,4,0,5,-6,7,-10,11};
int i=0,n=10,sumtillnow=arr[0],sum=arr[0],start=0,end=0;
while(i<n)
{
sum=sum+arr[i];
if(abs(arr[i]-0) < abs(sumtillnow))
{
start=i;end=i;
}
if(abs(sumtillnow - 0) >= abs(sum - 0))
{
sumtillnow=sum;
end=i;
}
i++;
}
printf("the range is %d to %d",start,end);
getch();
}
#include<stdio.h>
#include<math.h>
#include<conio.h>
int main()
{
int arr[10]={-1,2,-3,4,0,5,-6,7,-10,11};
int i=0,n=10,sumtillnow=arr[0],sum=arr[0],start=0,end=0;
while(i<n)
{
sum=sum+arr[i];
if(abs(arr[i]-0) < abs(sumtillnow))
{
start=i;end=i;
}
if(abs(sumtillnow - 0) >= abs(sum - 0))
{
sumtillnow=sum;
end=i;
}
i++;
}
printf("the range is %d to %d",start,end);
getch();
}
yup.. this time microsoft seems to be in an easy mood... bt they are asking some irrelevant question... like how to chek if a tree is binary.. a post is on careercup,refering this irrelevant question,people are commenting its nonsense question made by poster himself.. bt believe me it is a microsoft question..
- rockstar September 06, 2012int find_max_sum(int *arr, int n)
{
int current_max, max_so_far,i;
int start=0,end =0;
current_max= max_so_far=0;
for(i=0;i<n,i++)
{
max_so_far+=a[i];
if(max_so_far<0){
max_so_far=0;start =++i;}
if(current_max<max_so_far)
{ current_max=max_so_far;
end = i;}
}
}
for(i=start;i<=end;i++)
printf("%d",arr[i]);
return;
1.take an array of 256 size,(for ascii charctrs),initialise with 0.
2.iterate through the string,increment the value of array by 1,on position pointd by ascii value of char obtained.
3.
do this for both string.
4.iterate through array of both strings,if same. than true else false..
time complexity o(n)
space complexity o(1){since int array is independent of string size}.
following are the test cases.. in case ny missing please point out
1.length zero not acceptable for ny of the side
2.should return scalene if a!=b!=c.
3.should return equilateral if a=b=c
4.should return isosceles if any two are equal.
5.negative edges not allowed.
firstly the answer to ur input case should be 15, 1, 11, -15, 18 rather than 15, 1, 11.... since sum is 30 in former case,and 27 in later..
here is the C CODE,executed correctly on VISUAL STUDIO 2010
//wap to find set of consecutive items in a given array wid largest sum..
#include<stdio.h>
#include<conio.h>
int sum(int *,int,int);
int main()
{
int a[5];
int i=0,j=0,s1=0,s2=0,beg=0,end=0;
printf("enter the array elements \n");
for(i=0;i<5;i++)
scanf("%d",&a[i]);
s1=a[0];
printf("numbers u entered are.. \n");
for(i=0;i<5;i++)
printf("%d ",a[i]);
for(i=0;i<5;i++)
{
j=4;
while(j>=i)
{
s2=sum(a,i,j);
if(s2>s1)
{
s1=s2;
beg=i;
end=j;
}j--;
}
}
printf("numbers are... \n");
for(i=beg;i<=end;i++)
printf("%d ",a[i]);
getch();
}
int sum(int *a,int i,int j)
{
int s=0;
for(i;i<=j;i++)
s=s+a[i];
return s;
}
first check if der is a loop wid o(n) complexity floyds theorem..
if loop is der,mark the starting node of loop wid pointr p.now tak a pointr k pointing to first node of lnkd list.traverse it until u rech p,increment countr til dat.after dis loop,point k to the next sequential node.. again run loop and increment counter untill p is rechd.. counter is the no. of nodes we wanted..
#include<stdio.h>
- rockstar November 23, 2012#include<conio.h>
int coins[101];
int coinc(int ,int );
void main(){
int n=0,x=0,i=0,amt=0;
printf("no of coins");
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&coins[i]);
printf("enter the amount");
scanf("%d",&amt);
x=coinc(amt,n-1);
printf("%d",x);
getch();
}
int coinc(int sum,int n)
{
if(sum >= coins[n])
{
return(1 + coinc(sum-n,n));
}
else if(sum < coins[n])
{
return(coinc(sum,n-1));
}
else if(n==0)
{
if(sum>0 && sum%coins[n]==0)return(sum/coins[0]);
}
else if(sum==0)
{
return 0;
}
else
{
return 0;
}
}