@ Ram Thats a cool version.
I shall work on improving my version below. Does anybody see any flaws in
the algorithm?
Summary: It starts looking at the array from the head and tails at tandem.
It does a single pass through the array swapping elements from head to tail
upon finding an appropriate element at the tail by going down the tail.
Regards
Ashutosh
//// Pseudo code of the algorithm
head = 0;
tail = sizeOfArray;
zeros = 0;
ones = 0;
for (head = 0; head < sizeOfArray; head++) {
if head is odd
{
if array[head] is 0
{
zeros = zeros + 1
if tail = head; tail = tail +1
while array[tail] is 0 {
tail = tail - 1
zeros = zeros +1
}
// tail is one
swap array[tail] & array[head]
ones = ones +1
// continue looping
}
else // array head is 1
{
// continue looping
if ones + zeros = sizeOfArray {
if ones <> zeroes imbalance = 1
exit // done or error occurred.
}
}
}
else // position is even
{
if array[head] is 1
{
ones = ones +1
if tail = head; tail = tail +1
while array[tail] is 1 {
tail = tail - 1
ones = ones +1
}
// tail is zero
zeros = zeros +1
swap array[tail] <-> array[head]
//continue looping
}
else // array head is 0
{
//continue looping;
if ones + zeros = sizeOfArray {
if ones <> zeroes imbalance = 1
exit // done or error occurred.
}
}
}
}
2010/8/19 ram das <ramnaraya...@gmail.com>
> {
> int odd=1,even=0;
> while(odd <= size && even <=size)
> {
> if ( arr[even] != 1 )
> even+=2;
> if ( arr[odd] != 0 )
> odd+=2;
> if ( arr[even] == 1 && arr[odd] == 0 )
> {
> arr[even]=0;
> arr[odd]=1;
> }
> }
> }
>
> On Thu, Aug 19, 2010 at 7:00 PM, ram das <ramnaraya...@gmail.com> wrote:
>
>> shiftZeroOne(int *arr,int size)
>>
>> {
>> int odd=1,even=0;
>> while(odd <= size && even <=size)
>> {
>> if ( arr[even] != 1 )
>> even+=2;
>> if ( arr[odd] != 0 )
>> odd+=2;
>> if ( arr[even] == 1 && arr[odd] == 0 )
>> {
>> arr[even]=0;
>> arr[odd]=1;
>>
>> }
>> }
>> }
>>
>>
>>
>>
>> On Thu, Aug 19, 2010 at 5:53 PM, Rais Khan <raiskhan.i...@gmail.com>wrote:
>>
>>> void ArrayShifting(int *str, int size)
>>> {
>>> int odd=1, even=0;
>>> while(odd < size)
>>> {
>>> int position;
>>> if(str[even]!=0)
>>> {
>>> position = even+1;
>>> while(position < size)
>>> {
>>> if(str[position]==0)
>>> { str[position]=1;str[even]=0;break;}
>>> position = position+2;
>>> }
>>> }
>>> even = even+2;
>>> if(str[odd]!=1)
>>> {
>>> position = odd+1;
>>> while(position < size)
>>> {
>>> if(str[k]==0)
>>> { str[position]=0;str[odd]=1;break;}
>>> position = position+2;
>>> }
>>> }
>>> odd=odd+2;
>>> }
>>> }
>>>
>>> This code seems working for me, If you agree then we can work on
>>> measuring the complexity & improving the code accordingly.
>>>
>>>
>>>
>>>
>>> On Thu, Aug 19, 2010 at 5:27 PM, Ashutosh Tamhankar <
>>> asshuto...@gmail.com> wrote:
>>>
>>>> Hi Amit
>>>>
>>>> Am I allowed to keep counters to count the number of 1's and 0s right?
>>>>
>>>> The condition of not using extra memory is for the array!?
>>>>
>>>> Regards
>>>> Ashutosh
>>>>
>>>>
>>>> 2010/8/18 amit <amitjaspal...@gmail.com>
>>>>
>>>> you are given an array of integers containing only 0s and 1s. you have
>>>>> to place all the 0s in even position and 1s in odd position and if
>>>>> suppose no if 0s exceed no. of 1s or vice versa then keep them
>>>>> untouched. Do that in ONE PASS and WITHOUT taking EXTRA MEMORY.
>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To post to this group, send email to algoge...@googlegroups.com.
>>>>> To unsubscribe from this group, send email to
>>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
>>>> To unsubscribe from this group, send email to
>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> Thanks & Regards
>> Ram Narayan Das
>> mob: +91 9177711195
>>
>
>
>
> --
> Thanks & Regards
> Ram Narayan Das
> mob: +91 9177711195
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.
