shoonya.mohit
BAN USER1. 000001001 --> BAD
2. 001101001 --> ??
3. 000101001 --> CAD
This is 1 variation of Dyck language
http : // en . wikipedia . org / wiki / Catalan_number //remove spaces
chck the recurrence relation given in this page...
Sorry !
didn't read the question properly...
right !
simple and sleek
#include<stdio.h>
#include<string.h>
void reverse(char *arr, int start, int end)
{
int i=0;
char temp;
if(end<=start) return;
while(i<=(end-start)/2)
{
temp = arr[start+i];
arr[start+i]=arr[end-i];
arr[end-i]=temp;
i++;
}
}
void reverse_string(char *arr)
{
int first=0, last=0;
while(1)
{
while(arr[last]!='\0' && arr[last]!=' ')
last++;
reverse(arr, first, last-1);
if(arr[last]=='\0') return;
first=last+1; last++;
}
}
int main()
{
char *foo = "I am a fool";
printf("before: foo[%s]\n", foo);
reverse_string(foo);
printf("aftre: foo[%s]\n", foo);
return 0;
}
Complexity: O(n)
- shoonya.mohit July 06, 2010@Umang
this is not O(log n) algo..
typo in above post
eg no=16704 can be represented as
01000001 01000000 -- MSB LSB
01000000 01000001 -- LSB MSB
plz consider this !
can you pl explain the logic ?
- shoonya.mohit May 13, 20101. take slow and fast pointer, and find the mid-point //O(n)
2. reverse the list from mid-point till last //O(n)
3. check for palindrome // O(n)
4. again reverse the second half to get original list // O(n)
Total T.C = O(n)
awesome !!
- shoonya.mohit May 12, 2010void foo(int n)
{
if(n<=9)
printf("%d ", n);
else
{
foo(n/10);
printf("%d ", n%10);
}
}
void foo(int n)
{
if(n<=9)
printf("%d ", n);
else
{
foo(n/10);
printf("%d ", n%10);
}
}
what about repetition ?
won't it print same sequence more than one time ?
use general tree structure
node->child
node->sibling
//same as trie DS
adding more
1. all basic functions. eg play, pause, FF/REW, eject, stop.
2. all cross cases. eg push FF/REW when loading/stopped/reading etc
3. power off while different state //play, pause, stop etc
4. voltage fluctuation
5. different formats of DVD
6. scratched DVD
7. varying Temp/humidity etc
8. connectivity with different brands of TV
@ananymous
consider RED=0, BLUE=1
sequence is
0111100000
then your algo will do 5 swap to bring it to 00000011111
but rather efficient way will be 11111000000 // 1 swap
-----
so, why not do like this
1. do a full scan, count no of red/blue
2. another scan and check, red-first or blue-first, which will take less swap
3. then follow any 0(n) algo of keeping two pointers and swap, when mismatch
still it's O(n) only...
Comments ?
step 1: sort the array //O(n.log(n))
arr=2,5,3,1,8,7,5,4 --> 1,2,3,4,5,5,7,8
//size=8
step 2:
i=0, j=7
if a[i]+a[j]==K //done
if a[i]+a[j] > K //j--
if a[i]+a[j] < K //i++
repeat step2, till it reaches mid point //O(n)
for #1 1st part
use
- shoonya.mohit December 10, 2010