gurumukhi
BAN USER- 0of 0 votes
AnswersA Matrix of cells is given. A cell may be desert (represented as 1) or forest (represented as 0). Now every year all forests adjacent to desert convert to deserts. You are supposed to find out how many forests will be there after 'k' years (also give their location).
- gurumukhi in India
** : on phone interview, interviewer will ask you to code on the online real-time editors like collabedit.com, sync.in or docs.google.com| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Algorithm
1. sort array in O(nlogn)
2. remove duplicate elements in one go O(n)
curr=1; i=1; // ignoring first element, which is not repetition
while(i<n)
{
if(arr[i]!=a[i-1])
{
if(curr!=i)
arr[curr]=arr[i];
curr++;
i++;
}
else
i++;
}
3. now curr is the length of final array, which has no repetition
using this we print final subsets
for(i=0 ; i<curr-2 ; i++)
for(j=i+1 ; j<curr-1 ; j++)
for(k=j+1 ; j<curr ; k++)
printf("[%d,%d,%d]\n",arr[i].arr[j],arr[k]);
#include<stdio.h>
#include<string.h>
main()
{
int i,curr,cnt;
char arr[100],ch;
scanf("%s",arr);
ch=arr[0]; cnt=curr=0;
for(i=0;i<=strlen(arr);i++)
{
if(arr[i]==ch) { cnt++; }
else
{
if(cnt>0) arr[curr++]=ch;
if(cnt>1) arr[curr++]=cnt+48;
cnt=1;
ch=arr[i];
}
}
if(cnt>0) arr[curr++]=ch;
if(cnt>1) arr[curr++]=cnt-48;
arr[curr-1]='\0';
printf("%s",arr );
}
@Anonymous yes the complexity of above codes is O(n^3), and its considered as better than O(2^n)..
- gurumukhi April 02, 2013I think we can't do it in better complexity than O(n^3)..