k2
BAN USERwith somewhat analysis you an appreciate its similarity with 'printing the permutations of a string'. Here also for each player decisions can be made wrt the previous player's followers and for only current player. local hash arrys can be maintained and referenced for subsequent players. Below is the working code tested in C:
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
int min(int,int);
int func(int i,int j,int k,int n,int **matrix,int *hash,int *count);
int main()
{
int i,j,k,**matrix,temp,temp1,*hash,count;
printf("enter the values for number of(players,followers and desired followers i,j,k)\n");
scanf("%d%d%d",&i,&j,&k);
matrix=(int **)malloc(i*sizeof(int *));
for(temp=0;temp<i;temp++)
matrix[temp]=(int *)malloc(j*sizeof(int));
printf("enter the values\n");
for(temp=0;temp<i;temp++)
{
for(temp1=0;temp1<j;temp1++)
scanf("%d",&matrix[temp][temp1]);
printf("\n");
}
printf("values added are\n");
hash=(int *)malloc(j*sizeof(int));
for(temp=0;temp<i;temp++)
{
for(temp1=0;temp1<j;temp1++)
{
printf("%d ",matrix[temp][temp1]);
hash[temp1]=0;
}
printf("\n");
}
count=0;
printf("minimum number of players required are:%d",func(0,j,k,i,matrix,hash,&count));
getch();
return 1;
}
int func(int i,int j,int k,int n,int **matrix,int *hash,int *count)
{
if(i>=n)
return -1;
int *hash1,tCount,t;
hash1=(int *)malloc(j*sizeof(int));
for(t=0;t<j;t++)
{
if(matrix[i][t]==1)
{
hash1[t]=1;
tCount++;
if(hash[t]!=1)
{
hash[t]=1;
*count++;
}
if(tCount==k||*count==k)
return 1;
}
else
{
hash1[t]=0;
}
}
return min(func(i+1,j,k,n,matrix,hash,count),1+func(i+1,j,k,n,matrix,hash1,&tCount));
}
int min(int x,int y)
{
return (x<y&&x!=-1)?x:y;
}
output:
=======
enter the values for number of(players,followers and desired followers i,j,k)
3 6 5
enter the values
1 1 1 1 0 0
0 0 0 0 1 0
1 1 1 1 1 0
values added are
1 1 1 1 0 0
0 0 0 0 1 0
1 1 1 1 1 0
minimum number of players required are:1
DP solution
1) Maintain a 2D (N*N) binary hash for a string of size N and initialize to -1.
2) Iterate recursively such that at a particular iteration for two indexes p and q, if str[p]==str[q] refer/compute
hash if str[p+1]...str[q-1] is palindrome.
3) handle edge cases (like q<p).
bool func(char *str,char **hash,int i,int j,int *max,int *I)
{
if(i>j) return 1;
if(hash[i][j]!=-1) return hash[i][j];
if(str[i]==str[j] && func(str,hash,i+1,j-1,max,I)==1)
{
hash[i][j]=1;
if(j-i>*max)
{
*max=j-i;
*I=i;
}
return hash[i][j];
}
else
{
hash[i][j]=0;
return (func(str,hash,i+1,j-1,max,I)|| func(str,hash,i,j-1,max,I));
}
}
- k2 July 14, 20131)consider an array of n integers.
2) create a hash of n entries with value as number of digits for each integer element in arr.
3)iterate in N^2 fashion for all un-appended elements. (think on this why 2 loops!!)
4) in the inner loop, find the maximum leftmost digit.
5) in case of a tie, keep a utility method handy to resolve them.
6) keep on appending the integers to a string (u can always write one!!).
7) update hash for all appended entries with -1.
following code snippet gives only an idea (not tested on compiler):
//utility method to return number of digits for an element
int nDigits(int num)
{
int n=0;
while(num>0)
{
num/=10;
n++;
}
return n;
}
//utilty method to return indexed digit of an element
int iDigit(int num,int index)
{
int n,rem;
for(int i=1;i<=index;i++)
{
rem=num%10;
num/=10;
}
}
//utility method to break a tie
int compare(int *arr,int fIndex,int sIndex,int f, int s)
{
if(f==0)
return fIndex;
if(s==0)
return sIndex;
x=iDigit(arr[fIndex],f);
y=iDigit(arr[sIndex],s);
if(x==y)
return compare(arr,fIndex,sIndex,f-1,s-1);
else
return fIndex?x>y:sIndex;
}
1st step:
==========
create hash of number of digits:
=================================
arr[n];//lets assume
for(i=0;i<n;i++)
hash[i]=nDigits(arr[i]);
2nd step:
==========
iterations:
=============
for(i=0;i<n;i++)
{
max=-1;index=-1;
for(j=0;j<n;j++)//in each iteration will find one entry
{
if(hash[j]!=-1)
{
x=iDigit(arr[j],hash[j]);
if(x>max)
{
max=x;
index=i;
}
if(x==max)
{
y=compare(arr,index,j,hash[index],hash[j]);
index=y;//we already have max
}
}
hash[index]=-1;
append(str,arr[index])
}
}
Idea would be to recognize the branch on which the given element lies. Use a simple pre-order traversal to store elements in stack (maximum size: depth of a tree).
Once we have the corresponding branch including the given element one can print the elements at a distance (k-(distance of current node and given node)). Below code gives and idea.
PS: this code is not tested and intent is to give an idea:
//this method is to populate stack with required branch elements
bool func(struct tNode *ptr,int *stack,struct tNode *res)
{
if(ptr==NULL)
return False;
if(ptr==res||func(ptr->left,stack,res)||func(ptr->right,stack,res))
{
push(stack,ptr);
return True;
}
return False;
}
//This method is to print elements at k distance from a particular node
void printElem(struct tNode *ptr,struct tNode *par,int d,int k)
{
if(ptr==NULL||ptr==par)
return;
if(d+1==k)
{
printf("\n%d",ptr->num);
return;
}
printElem(ptr->left,par,d+1,k);
printElem(ptr->right,par,d+1,k);
}
int main()
{
struct tNode *stack[<depth of tree>],*temp,*prev;
int d,k;
func(root,stack,res);
temp=NULL;
d=5;
k=0;
while(!isEmpty(stack)&&k<=n)
{
prev=pop(stack);
printElem(p,temp,0,d-k);
k++;
}
}
Solution can be devised through dynamic programming. Maintain a 2-D hash of m*n such that each location (if not zero) contains the distance to reach the destination.
Will be divided into two steps:
1) recursively creating the hash.
2) Recursively traversing the hash to print elements.
Below code gives an idea for 1st step. 2nd step can be coded easily on similar lines.
int func(in i,int j,int pr,int pc,int m,int n,int fr,int fc,int arr[][],int hash[][])
{
int temp[4];min,k;
if(i<0||i>m||j<0||j>n||(i==pr&&j==pc))
return 0;
if(i==fr&&j==fc)
{
hash[i][j]=1;
return 1;
}
if(hash[i][j]!=-1)
return hash[i][j];
if(arr[i][j]==0)
{
hash[i][j]=0;
return 0;
}
min=0;
temp[0]=func(i,j+1,i,j,m,n,fr,fc,arr,hash);
temp[1]=func(i,j-1,i,j,m,n,fr,fc,arr,hash);
temp[2]=func(i+1,j,i,j,m,n,fr,fc,arr,hash);
temp[3]=func(i-1,j,i,j,m,n,fr,fc,arr,hash);
//choose the minimum positive
for(k=0;k<4;k++)
{
if(temp[k]!=0)
{
if(min==0||min>temp[i])
min=arr[i];
}
}
if(min==0)
{
hash[i][j]=0;
return 0;
}
hash[i][j]=min+1;
return min+1;
}
1st method: merge sort
take two rows at a time and merge adding check for repetitions. This will require maintaining two arrays of size m*n and need to switch between them. T(m*n) S(m*n) however constants and space requirements are high.
2nd method: maintain a min-heap
maintain 2 arrays of size m. one will store the row index of elements in a min heap and other the corresponding column index. solution can be devised in following 3 steps:
1) Initialize a min Heap.
2) Make a min Heap
3) Pop elements and store in resultant array.
Below code gives an idea.
int main()
{
int arr[m][n],hashRow[m],minArr[m],resArr[m*n],i,j;
i=0;
1st step
while(i<m)
{
j=0;
while(j<n)
{
if(!isUnique(minArr,arr[i][j])) //---------T(m)
j++;
else
{
minArr[index]=i;
hashRow[i]=j;
index++;
break;
}
}
}
// 2nd step
makeMinHeap(minArr,hashRow,index-1); //--------------T(mlogm)
//3rd step
while(index>=0)
{
resArr[count++]=minArr[0];
i=minArr[0];
j=resArr[i]+1;
while(j<n)
{
if(!isUnique(minArr,arr[i][j]))
j++;
else
{
minArr[0]=arr[i][j];
hashRow[i]=j;
break;
}
}
if(j=n)
{
minArr[0]=minArr[index];
index--;
}
restoreDown(minArr,index,0); //-------------------T(m*nlogm)
}
}
just like a normal level order traversal..maintain a queue. Use some extra variable to track, how elements are to be printed viz. for even level they be printed in the same sequence they are present in queue and for odd level they are printed in reverse order.
void func(struct node *ptr)
{
if(ptr==NULL)
return;
int n;
n=numNodes(ptr);
struct node *arr[n]={NULL}; //n is the number of nodes in tree..initialize array to NULL
int cl,nl,level,count,index,p,q,i;
arr[0]=ptr;
nl=count=index=0;
p=q=0;
cl=1;
while(arr[index]!=NULL)
{
if(level==0)
printf("%d",arr[0]->num);
cl--;
if(arr[index]->left!=NULL)
{
arr[++count]=ptr->left;
nl++;
}
if(arr[index]->left!=NULL)
{
arr[++count]=ptr->right;
nl++;
}
if(cl==0)
{
p=q;
q=index;
cl=nl;
nl=0;
if(!(level%2)) //even level
{
i=p+1;
while(i<=q)
{
printf("%d",arr[i]->num);
i++;
}
}
else //odd level
{
i=q;
while(i>p)
{
printf("%d",arr[i]->num);
i--;
}
}
level++;
}
index++;
}
}
At each step, one can take either one step or two steps. A simple Dynamic programming approach can be used.
Below is the working C code for n==6:
#include<stdio.h>
#include<conio.h>
int main(int n)
{
int temp;
int hash[7]={0};
hash[0]=hash[1]=1;
temp=func(6,hash);
printf("%d",temp);
getch();
return 1;
}
int func(int n,int hash[])
{
if(hash[n]!=0)
return hash[n];
int ways;
ways=0;
ways+=func(n-2,hash);
ways+=func(n-1,hash);
hash[n]=ways;
return hash[n];
}
Time complexity O(N*2).
Maintain the difference of Ci-Di for each station in an array. Then for each element in the array traverse the remaining array in a circular fashion so that at no point the residual fuel is negative. Below code gives an idea and prints all the valid points. Can be modified to return the first node also.
void func(int ci[],int di[],int n)
{
int diff[n],i,j,s,flag;
for(i=0i<ni++)
temp[i]=ci[i]-di[i];
flag=0;
for(i=0;i<n;i++)
{
if(diff[i]>=0)
{
s=arr[i];
j=(i+1)%n;
while(j!=i)
{
s+=arr[j];
if(s<=0)
break;
}
if(j==i)
{
flag++;
printf("\n valid position :%d",i);
}
}
}
if(!flag)
printf("no valid position found");
return;
}
int diameter(struct node * tree)
{
/* base case where tree is empty */
if (tree == 0)
return 0;
/* get the height of left and right sub-trees */
int lheight = height(tree->left);
int rheight = height(tree->right);
/* get the diameter of left and right sub-trees */
int ldiameter = diameter(tree->left);
int rdiameter = diameter(tree->right);
/* Return max of following three
1) Diameter of left subtree
2) Diameter of right subtree
3) Height of left subtree + height of right subtree + 1 */
return max(lheight + rheight + 1, max(ldiameter, rdiameter));
}
- k2 March 02, 2014