Ajay
BAN USER- 0of 0 votes
AnswersCheck whether a linkedlist is pallindrome or not, recursively?
- Ajay in United States| Report Duplicate | Flag | PURGE
Algorithm
I came up with a solution without recursion. It takes O(n^2) time.
#include<stdio.h>
int LPS(char *s,int n);
int main()
{
char array[100];
char c;
int i = 0;
c = getchar();
while(c!='\n')
{
array[i++]=c;
c = getchar();
}
array[i] ='\0';
int n = i;
int l = LPS(array,n);
printf("%d\n",l);
return 0;
}
int LPS(char *s,int n)
{
int x = 0;
int i ,k = 2;
int count = 1;
int max = -500;
int j = 0;
for(i=1;i<n-1;i++)
{
if(s[j]==s[k] && j>=0 && k<=n-1)
{
count += 2;
j--;
k++;
i--;
if(count > max)
{
max = count;
}
if(j<0)
{
count = 1;
i = k-2;
j = i;
}
}
else if(s[k]==s[i])
{
count += 1;
k++;
i--;
if(count > max)
{
max = count;
}
}
else
{
k++;
i = k-2;
j = i;
count = 1;
}
}
if(count>max)
{
max = count;
}
return max;
}
1) Make a 1-d array which will keep count the number of one in a row.
2) scan each row and store the count, e.g., let's say zeroth row contains 3 1's then a[0] will be 3.
3) now find the maximum sum of the contigous subarray but the subarray should not contain a zero.
4) the index of 1d array 'a' on which sum is maximum will give the index of rows.
Correct me if i am wrong
obviously the matrix itself will give that submatrix which has most number of 1s (if all row contains at least one 1). We can break the matrix in those submatrix which comes before or after a row such that the row contains all zero..
I guess this question on geeksforgeeks
geeksforgeeks/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/
is different from what it is asked.. Please Correct me if i am wrong..
We can't do it in a single weigh but if there are 8 bottles and 1 bottle weigh different than the other 7, then we can find it in 2 weighs.
- Ajay July 07, 20141) Divide the 8 bottles in a group of 3,3,2
2) weigh group of 3 and 3, if the weight is equal then the bottle is present in the other group of 2 and we can determine in one more step.
3) if the bottle is present in one of the group in 3, then choose 2 bottles at random from this group weigh them if the weight is equal, the defected bottle is the other one which we left else we have found the bottle in group of two.