dutch national flag problem :)
On Sat, Sep 24, 2011 at 3:45 PM, Dheeraj Sharma <dheerajsharma1...@gmail.com
> wrote:
> i think this travels only once ... correct me if am wrong
> #include<stdio.h>
> #include<string.h>
> #define SWAP(a,b,c) (c)=(a),(a)=(b),(b)=(c)
> int main()
> {
> int t,x;
> scanf("%d",&t);
> while(t--)
> {
> char str[100];
> scanf("%s",str);
> int i=0,j=0,k=strlen(str)-1;
>
> while(str[i]=='0')
> i++;
> while(str[k]=='2')
> k--;
>
> j=i;
> while(j<=k)
> {
> if(str[j]=='2')
> {
> SWAP(str[j],str[k],x);
> k--;
> }
>
> if(str[j]=='0')
> {
> SWAP(str[i],str[j],x);
> i++;
> }
> if(str[j]!='2')
>
> j++;
> }
>
> printf("%s\n",str);
> }
> return 0;
>
> }
>
>
> On Sat, Sep 24, 2011 at 11:39 AM, Yogesh Yadav <medu...@gmail.com> wrote:
>
>> we cant traverse the string twice...
>>
>> if there is an error in my logic then plz tell....
>>
>> my logic is:
>> we have to take starting and ending indexes for '0','1','2' like below
>>
>> 0 1 2
>> starting_index
>> ending_index
>>
>>
>> now suppose our string "102112011"
>>
>> so we start from the left and traverse the whole string
>>
>> first character ='1'
>>
>> 0 1 2
>> starting_index 0
>> ending_index 0
>>
>> next character = '0'
>>
>> 0 1 2
>> starting_index 1 0
>> ending_index 1 0
>>
>> ( ending_index0 > ending_index1 ) so we swap the numbers according to
>> Starting_index not according to Ending_index
>> So it will become
>>
>> 0 1 2
>> starting_index 0 1
>> ending_index 0 1
>>
>> and string will become "01"
>>
>> next character '2'
>>
>> 0 1 2
>> starting_index 0 1 2
>> ending_index 0 1 2
>>
>> (ending_index0<ending_index1<ending_index2) so ending indexes in
>> increasing order...so no need to swap
>>
>> so string is now "012"
>>
>> next character '1'
>>
>>
>> 0 1 2
>> starting_index 0 1 2
>> ending_index 0 3 2
>>
>> (ending_index1>ending_index2) so we swap the current 1 with starting index
>> of 2
>> so string will become "0112"
>>
>> 0 1 2
>> starting_index 0 1 3
>> ending_index 0 2 3
>>
>> next character '1'
>>
>> 0 1 2
>> starting_index 0 1 3
>> ending_index 0 4 3
>>
>> (ending_index1>ending_index2) so we swap the current 1 with starting index
>> of 2
>>
>> so string will become "01112"
>>
>> 0 1 2
>> starting_index 0 1 4
>> ending_index 0 3 4
>>
>> next character '2'
>>
>> 0 1 2
>> starting_index 0 1 4
>> ending_index 0 3 5
>>
>> (ending_index0<ending_index1<ending_index2) so no swap
>>
>> so string will become "011122"
>>
>> next character '0'
>>
>>
>> 0 1 2
>> starting_index 0 1 4
>> ending_index 6 3 5
>>
>>
>> (ending_index0>ending_index1>ending_index2) so we swap the current 0 with
>> staring index of 2 first and then with starting index of 1
>> so string will become "0011122"
>>
>> 0 1 2
>> starting_index 0 2 5
>> ending_index 1 4 6
>>
>>
>> and so on.... i hope its much explained...
>>
>>
>> ....
>>
>>
>> On Sat, Sep 24, 2011 at 10:30 AM, Dheeraj Sharma <
>> dheerajsharma1...@gmail.com> wrote:
>>
>>> char str[100],t;
>>> scanf("%s",str);
>>> char ch='0';
>>> int i=0,j=0;
>>> while(j<strlen(str))
>>> {
>>> if(str[j]==ch)
>>> {
>>> SWAP(str[i],str[j],t);
>>> i++;
>>> }
>>> j++;
>>> }
>>> ch='1';
>>> j=i;
>>> while(j<strlen(str))
>>> {
>>> if(str[j]==ch)
>>> {
>>> SWAP(str[i],str[j],t);
>>> i++;
>>> }
>>> j++;
>>> }
>>> printf("%s\n",str);
>>>
>>>
>>> On Sat, Sep 24, 2011 at 9:55 AM, Anup Ghatage <ghat...@gmail.com> wrote:
>>>
>>>> Is this like the segregating all the 1's to the right and the 0's to the
>>>> left
>>>> or am i missing something?
>>>>
>>>>
>>>> On Sat, Sep 24, 2011 at 9:39 AM, VIHARRI <viharri....@gmail.com> wrote:
>>>>
>>>>> You are given a string (consisting of 0's, 1's or 2's) where 0
>>>>> represents a blue ball, 1 a
>>>>> red ball, and 2 a black ball. Using only swap operations (counting
>>>>> sort not allowed)
>>>>> rearrange the string such that all blue balls are together on one
>>>>> side, followed by all red
>>>>> balls, and then all black balls. You can iterate through the string
>>>>> only once.
>>>>> Eg 102112011 should produce 001111122?
>>>>>
>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>>> To unsubscribe from this group, send email to
>>>>> algogeeks+unsubscr...@googlegroups.com.
>>>>> For more options, visit this group at
>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>
>>>>>
>>>>
>>>>
>>>> --
>>>> Anup Ghatage
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>> To unsubscribe from this group, send email to
>>>> algogeeks+unsubscr...@googlegroups.com.
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>
>>>
>>>
>>> --
>>> *Dheeraj Sharma*
>>> Comp Engg.
>>> NIT Kurukshetra
>>>
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> *Dheeraj Sharma*
> Comp Engg.
> NIT Kurukshetra
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
