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 <[email protected]> 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 <
> [email protected]> 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 <[email protected]> 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 <[email protected]> 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 [email protected].
>>>> To unsubscribe from this group, send email to
>>>> [email protected].
>>>> 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 [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected].
>>> 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 [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
