a.khan
BAN USERC: capacity of each cup
M: total flow of water
n: the cup for which amount of water is required.
float cupfill(int C,int M,int n){
int i,level=1,count=1;
float *cups=malloc(n*sizeof(float));
for(i=0;i<n;i++)cups[i]=0;
cups[0]=M; //first put all water in first cup, which may cause overflow
for(i=0;i<n-1;i++){
if(cups[i]>C){ //if cup overflows
float flow=(cups[i]-C)/2.0;
cups[i]=C;
//distribute overflow among children
cups[i+level]+=flow;
cups[i+level+1]+=flow;
}
if(level==count){ //keeping track of the level
count=1;
level++;
if(i+level>n)break; //if we have calculated everything upto the parents of n, we know how much n holds
}
else count++;
}
if(cups[n-1]>C) return C;
else return cups[n-1];
}
What does it mean by no extra space? Does it mean that we should not use any extra space for creating the BST nodes, rather the BST nodes are already given the pre-order list, we just have to set the left and right childs properly.
Or is it that except for creating BST nodes we should not use any extra space?
Fairly simple logic. The resulting string sum will have length max(|a|,|b|)+1. We start the sum from right hand side(LSB), and move to left towards MSB.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char *binary_add(const char *a,const char *b){
int a_len=strlen(a);
int b_len=strlen(b);
int max_len=(a_len>b_len)?a_len:b_len; // finding the max length of a and b, the sum will be of max_len+1 size
char *sum=malloc((max_len+1)*sizeof(char));
int carry=0;
int i=max_len;
a_len--;
b_len--;
while(i>=0){
if(a_len<0 && b_len<0){ //for the leftmost digit,only the carry is considered
sum[i]='0'+carry;
}
else if(a_len<0){ // we consider cases when both the binary strings are not equal length and one ends before the other
sum[i]='0'+(b[b_len]-'0'+carry)%2;
carry=(b[b_len]-'0'+carry)/2;
b_len--;
}
else if(b_len<0){
sum[i]='0'+(a[a_len]-'0'+carry)%2;
carry=(a[a_len]-'0'+carry)/2;
a_len--;
}
else{
sum[i]='0'+(a[a_len]-'0'+b[b_len]-'0'+carry)%2;
carry=(a[a_len]-'0'+b[b_len]-'0'+carry)/2;
a_len--;
b_len--;
}
i--;
}
return sum;
}
int main(){
const char *a="11";
const char *b="1000";
char *sum=binary_add(a,b);
printf("%s + %s=%s\n",a,b,sum);
return 0;
}
We can keep a field called 'seen' in every list node. This may provide an alternative solution, writing the rough pseudo-code here:
node *find_intersection(node *list1,node *list2){
while(list1!=NULL || list2!=NULL){
if(list1->seen==1) return list1;
if(list2->seen==1) return list2;
list1->seen=1;
list2->seen=1;
if(list1!=NULL)list1=list1->next;
if(list2!=NULL)list2=list2->next;
}
}
Maximum sum sub-sequence problem:
The solution is based on the recursive definition of:
max_subsequence_sum(a[left... right]) = max{a[left]+max_subsequence_sum(a[left+2,....right]), max_subsequence_sum(a[left+1,...right])};
The code user Dynamic program paradigm to calculate the solution and display the sequence:
#include <stdio.h>
#define MAX 9
int main(){
int a[MAX]={10,3,9,11,4,7,6,2,8};
int part_sum[MAX]; //holds all the part sums part_sum[i] holds max sum of a[i....n]
int taken[MAX]={0}; //denotes whether a particular element is taken in the part sum or not in the max sum of a[i....n]
int temp1,temp2,i;
for(i=MAX-1;i>=0;i--){
if(i==MAX-1){
part_sum[i]=a[i];
taken[i]=1;
}
else if(i==MAX-2){
if(a[i]>a[i+1]){
part_sum[i]=a[i];
taken[i]=1;
}else{
part_sum[i]=a[i+1];
taken[i]=0;
}
}
else{
temp1=a[i]+part_sum[i+2];
temp2=part_sum[i+1];
if(temp1>temp2){
part_sum[i]=temp1;
taken[i]=1;
}
else{
part_sum[i]=temp2;
taken[i]=0;
}
}
}
printf("Maximum sum possible is: %d\n",part_sum[0]);
printf("\nThe maximum subsequence is:\n");
i=0;
while(i<MAX){
if(taken[i]==0)i=i+1;
else{
printf("%d,",a[i]);
i=i+2;
}
}
return 0;
}
The code of the solution in c using Dynamic Programming:
#include<stdio.h>
int main()
{
// a holds the grass values
int a[4][4]={
{ 1,7,5,2 },
{ 5,12,3,6 },
{ 100,9,23,16 },
{ 16,4,5,9 },
};
int m=4,n=4;
// sum[i][j] holds the maximum grass that can be eaten if the goat goes from a[i][j] point to a[m-1][n-1]
// sum[0][0] == the maximum amount of grass the goat eats
// we build the matrix sum using dynamic programming paradigm
int sum[m][n];
// move[i][j] stores the next best move from a[i][j], that will allow the goat to eat maximum grass on its path from a[i][j] to a[m-1][n-1]
// move[i][j]='r' : move right
// move[i][j]='d' : move down
char move[m][n];
// calculate the solution and max grass to eat using the relation: sum[i][j] = a[i][j] + max(sum[i-1][j],sum[i][j-1])
int i,j;
for(i=m-1;i>=0;i--){
for(j=n-1;j>=0;j--){
if(i == m-1 && j == n-1 ){
sum[i][j] = a[i][j];
}
else if(i == m-1 ){
sum[i][j] = a[i][j] + sum[i][j+1];
move[i][j]='r';
}
else if(j == n-1 ){
sum[i][j] = a[i][j] + sum[i+1][j];
move[i][j] = 'd';
}
else if(sum[i][j+1]>sum[i+1][j]){
sum[i][j]= a[i][j] + sum[i][j+1] ;
move[i][j] = 'r';
}
else{
sum[i][j]= a[i][j] +sum[i+1][j];
move[i][j]='d';
}
}
}
// Output the best move solution
i=0;
j=0;
while(i< (m-1) || j< (n-1)){
printf("\nEat: a[%d][%d]=%d\n",i,j,a[i][j]);
if(move[i][j]=='r'){
printf("move right\n");
j++;
}
else{
printf("move down\n");
i++;
}
}
printf("\nEa: a[%d][%d] = %d\n",i,j,a[i][j]);
printf("total grass eaten: %d\n",sum[0][0]);
return 0;
}
This is a recursive implementation of alternateMerge.. the final result is available in the list pointer l1. So the function does not return anything.
The implementation assumes the lists are of equal size, so if any of the list ends, the alternateMerge ends, ignoring the rest of the elements in the other list.
void alternateMerge(node *l1,node *l2)
{
if(l1==NULL || l2==NULL) return;
node *temp;
temp=l1->next;
l1->next=l2;
l2=l2->next;
l1->next->next=temp;
alternateMerge(temp,l2);
}
Say, the link lists are of length m and n.
The easiest way is to take each element of first linked list and compare with all the elements of 2nd LL. ... O(m*n)
Sorting the linked list is tougher, but if we can sort in O (n log n), then we sort both the lists and intersection can be found in O (m+n) time.
After sorting, we just go through both LL and compare the elements.
Thus total time complexity would be: O(m log m) + O(n log n) + O(m+n)
== O(m log m) if m > n
How to sort in n log n time??? Can use Merge Sort. Look for a merge sort that is optimized for LL.
The language of the question is totally confusing. Those who answered, can you please explain by example how do you perceive the array?
@Jumbo, your example array has n/2 unique elements and another element which is repeated n/2 times. Is this the correct representation of the problem?
We can use bitwise operations instead of division.
Assumption: The dividend and divisors are integers.
Assumption: The integers are positive and divisor is non-zero.
The logic is to keep left-shifting the divisor(b) and multiplying the quotient by two (by right shifting) until b becomes greater than dividend a.
Then adding the original value of b incrementally and adding 1 to the quotient each time, until b becomes greater than a.
#include <stdio.h>
int main(){
int a=41;
int b=6;
int c=b;
if(b>a) return 0;
int qnt=1;
while(b<=a){
printf("b=%d qnt=%d\n",b,qnt);
b=b<<1;
qnt=qnt<<1;
}
b=b>>1;
qnt=qnt>>1;
while(b<=a){
printf("b=%d qnt=%d\n",b,qnt);
b+=c;
qnt++;
}
b--;
qnt--;
printf("qnt=%d\n",qnt);
return 0;
}
@chukka.swathi, Thanks for pointing it out. The boundary case when rotation==0 (or rotation==array.lenth) can't be handled by the code. The problem is that the function find_rotation goes into an infinite loop when no rotation is there. This can be handled by putting an exit condition for the boundary condition:
if(start==end) return start;
The whole code is:
int find_rotation(int a[],int len){
int start=0;
int end=len-1;
int mid=(start+end)/2;;
while(a[mid]<=a[mid+1]){
if(start==end) return start;
if(a[mid]>a[start]) // the rotation is in the second subpart
start=mid;
else
end=mid;
mid=(start+end)/2;
}
return mid;
}
Moreover, there is a concern about handling of duplication of array elements in the sorted array. I have tried to cover this aspect in the modified code here, but not sure the code is foolproof. suggestions are welcome.
- a.khan December 19, 2010The code by Ramkumar is the best way to do it, using 3 string reverse and making it a O(n) affair. Each element in the array is accessed at least twice, because there are two reverse applied to each element. I was trying for a solution where each element will be accessed only once, hence making the factor 2 go away.
The idea,
Loop for K times:
{
1. Start with i=0
2. Any A[i] goes to A[(i+n) mod K]
3. j=(i+n) mod K
4. temp=A[j]
5. A[j]=A[i]
6. i=j
}
Note that if K (len) and n has some common factor, then this loop will rotate over the same elements again and again. This is avoided by using another variable turn which shifts the element to be properly placed next, when an element already placed is encountered.
The code:
void rotate(int A[],int len,int n)
{
int turn=-1;
// turn is used to ensure that our loop does not move over the same set of array
// elements when len and n have a common factor
int i=turn;
int j,temp,temp2;
for(int k=0;k<len;k++){
if(i==turn){
i++; // first starts from A[0]
turn++;
temp=A[i];
}
j=(i+n)%len;
temp2=A[j];
A[j]=temp;
temp=temp2;
i=j;
}
}
@rj,
When you say "which element is considered as the first element", I am assuming you are pointing to the amount of rotation that is given to the original sorted array. For example, if original array is A={1, 2, 3, 4} and rotated array is A'={3, 4, 1, 2} then we assume the original first element at A[2] now.
If the amount of rotation (k) is not given, then it can be found by the divide and conquer based routine:
int find_rotation(A)
in O(log n) time. See the code posted above. Then using that k, we start searching in the proper subarray.
Hope you were pointing to this issue only.
Comment to the previous quote:
If the array is rotated and sorted, then first the elements in a array will first increase,fall down suddenly to min value and then increase again.
Say 0... i is rotated from the tail. i+1.... n are original first elements of the array.
Compare the key K with A[0].
If K> A[0] then K lies between 0 to i.
If K < A[0] then K lies between i+1 to n.
The point of rotation k is given?
If so, we do binary search within one of the subparts.
If not, we first find out the point of rotation. ... O(log n)
Then we do binary search on the appropriate subpart... O(log n)
<pre lang="c" line="1" title="CodeMonkey47968" class="run-this">#include <stdio.h>
// This subroutine finds how many places (k) the sorted array is rotated
// uses divide and conquer to find k... takes O(log n) time
int find_rotation(int a[],int len){
int i=0;
int start=0;
int end=len-1;
int mid=(start+end)/2;;
while(a[mid]<a[mid+1]){
if(a[mid]>a[start]) // the rotation is in the second subpart
start=mid;
else
end=mid;
mid=(start+end)/2;
}
return mid;
}
// Doing a binary search ... O(log n)
int search(int a[],int start,int end,int key){
if(start > end) return -1; // returns -1 if key is not found
int mid=(start+end)/2;
if(a[mid]==key) return mid;
if(a[mid]>key) return search(a,start,mid-1,key);
else return search(a,mid+1,end,key);
}
int main()
{
int a[8]={5,6,7,8,1,2,3,4};
int key=7;
int k=find_rotation(a,8);
int res;
if(a[0]>key) //the key is in the subpart k+1... n
res=search(a,k+1,7,key);
else // The key is in subpart 0.... k
res=search(a,0,k,key);
printf("the key is found at position %d",res);
return 0;
}</pre>
Take the first element as pivot. run through the whole file to check how many elements are less than pivot and how many are greater. This will give an idea whether the median will be greater or less than the current pivot.
Now go for the next element in the file to make it pivot (use previos decisions to bound the range of elements dat can be possible candidates for median), run this way until for on pivot equal number of elements on both larger and smaller side are found..
What is the complexity of the topological sort? If there are n nodes, topological sort will basically be BFS of the graph which is of order O(|V|+|E|), now |E| can be of O(n^2) even in DAG. So will it be a O(n) solution? please correct me if I am wrong.
- a.khan November 28, 2011