GAURAV
BAN USERComputer Science student
This can be done using recursion. The idea is to keep track of ROOT to LEAF path.
Let me explain it to you with an example.
Let the given tree is like below.
1
/ | \
2 4 66
/ | \
3 6 3
/
10
/
11
/
12
/
13
now we recursively traverse the tree and store ROOT to LEAF path in an array.
In above example ROOT to LEAF paths are:
1,2,3,10,11,12,13
1,2,6
1,2,3
1,4
1,6
While traversing the tree, keep track of maximum continuous sequence.
Like in 1st recursive call, we have path array and length array(it stores the maximum length till the index).
1,2,3,10,11,12,13
1,2,3, 1, 2 , 3, 4
Now count the maximum length i.e. 4 and store in our answer MAX.
Similarly for other recursive calls do the same and update MAX if required.
At last MAX would be our required answer.
Time complexity:
If H is maximum height of tree and L are total number of leaf nodes.
Then worst case wold be of O(L*H)
If the array is infinite, that means we don't have proper bounds to apply binary search.
So in order to find position of key, first we find bounds and then apply binary search algorithm.
Let low and high be pointing to 1st element of array,
Now compare key with high index element,
->if it is greater than high index element then copy high index in low index and double the high index
->if it is smaller, then apply binary search on high and low indices found.
int find_position(int arr[],int key) // we don't know the size of array
{
int l=0,h=0,val;
val=arr[0];
while(val<k)
{
l=h;
h=2*h;
val=arr[h];
}
// after finding low and high indices, apply binary search between them
return binSearch(arr,l,h,k);
}
This would run in O(log n).
- GAURAV February 21, 2015It can be done using an auxillary array. For each element in array A, store product of previous elements in auxillary array store[] in first pass from left to right. And in second pass, keep product of elements from right to left.
Example A[]={5,7,8,2}, Store[]={1,1,1,1}
Now move from left to right and fill Store[] like this,
Store[]={1,5,35,280}
Store[i] gives the value of product of elements on left side of A[i], excluding A[i].
Now move from right to left, keep product of right elements in a variable and replace the product accordingly.
Take a look at my implementation for clear understanding :)
void replaceElem(int arr[],int n)
{
int *store = new int[n];
memset(store,1,sizeof(store)); // Initialize each cell with 1
int temp=1;
for(int i=0;i<n;i++) // this stores product of left elements excluding the element
{
store[i]=temp;
temp=temp*arr[i];
}
temp=1;
for(int i=n-1;i>=0;i--) // this
{
store[i]=temp*store[i];
temp=temp*arr[i];
arr[i]=store[i]; // it replace the appropriate value
}
free(store);
}
simple but tricky, right now lets assume that the range would be of positive numbers only.
store the given upper value and lower value in an array eg. in given case arr1[ ]={1,2,5} and arr2[ ]={1,3,6}, now do a level order traversal of tree and check whether corresponding nodes are in the range of array elements considering each level as the array index. Example,
level 1-> 1 1 is in range of arr1[0] and arr2[0]
level 2-> 2 ,3 2 and 3 are in range of arr1[1] and arr2[1]
level 3->4, 5, 6, 7 5 and 6 are in range but 4 and 7 are out of
range in arr1[2] and arr2[2] thus nullify them.
A nice and simple one, just need to consider all the edge cases. for eg. what if all elements are negative/zero. A single traverse would be enough while storing the start and ending index of continuous positive elements and their current sum.
My c++ implementation is :
void printSubset(int arr[],int n)
{
int i,sum=INT_MIN,current=0,start=0,end=0,s,e;
for(i=0;i<n;)
{
s=i;
while(i<n && arr[i]>0)
{
current+=arr[i];
i++;
}
e=i-1;
if(sum<current) // update indices if current sum exceeds the total one
{
sum=current;
start=s;
end=e;
current=0;
}
i++;
while(i<n && arr[i]<=0) // find the next positive number
i++;
}
if(end==-1) cout<<"All are negative or zero";
else cout<<start<<" "<<end;
}
Javeed, well explained, Thanks.
- GAURAV April 03, 2015