[algogeeks] Re: Minimal number of swaps

[Dave]

Use the quicksort algorithm: Set the swap counter to 0. Search from the 
beginning of the array for the first 0, and from the end of the array for 
the first 1. If the pointers cross, you are done; otherwise increment the 
swap counter and continue the searches.

On Tuesday, March 29, 2016 at 9:00:21 AM UTC-5, Régis Bacra wrote:
>
> This puzzle comes from a contribution on codingame.com (link to the puzzle 
> ). Any idea to 
> solve it efficiently?
>
> Given a list of 1 and 0, you must regroup all the 1 at the begin of the 
> list in a minimum number of steps. A step is the interchange of two 
> elements located at different positions.
> The expected result is the minimum number of steps required to obtain a 
> sorted list.
>
> Examples:
> 1 0 1 0 1 -> 1
> 0 1 0 1 1 1 0 -> 2
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

[algogeeks] Re: Minimal number of swaps

[icy`]

oh, nevermind, sorry ;P  you want the 1's at the beginning, not the end... 
  //friday

On Friday, April 22, 2016 at 4:07:53 PM UTC-4, icy` wrote:
>
> Hi,
> I'm not sure I understand the second example.  Shouldn't the second one 
> also produce an answer of  1 (swap the one in index 1 with the zero in the 
> last index)
> 0 *1* 0 1 1 1 *0*
>
> icy`
>
> On Tuesday, March 29, 2016 at 10:00:21 AM UTC-4, Régis Bacra wrote:
>>
>> This puzzle comes from a contribution on codingame.com (link to the 
>> puzzle ). Any 
>> idea to solve it efficiently?
>>
>> Given a list of 1 and 0, you must regroup all the 1 at the begin of the 
>> list in a minimum number of steps. A step is the interchange of two 
>> elements located at different positions.
>> The expected result is the minimum number of steps required to obtain a 
>> sorted list.
>>
>> Examples:
>> 1 0 1 0 1 -> 1
>> 0 1 0 1 1 1 0 -> 2
>>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

[algogeeks] Re: Minimal number of swaps

[icy`]

Hi,
I'm not sure I understand the second example.  Shouldn't the second one 
also produce an answer of  1 (swap the one in index 1 with the zero in the 
last index)
0 *1* 0 1 1 1 *0*

icy`

On Tuesday, March 29, 2016 at 10:00:21 AM UTC-4, Régis Bacra wrote:
>
> This puzzle comes from a contribution on codingame.com (link to the puzzle 
> ). Any idea to 
> solve it efficiently?
>
> Given a list of 1 and 0, you must regroup all the 1 at the begin of the 
> list in a minimum number of steps. A step is the interchange of two 
> elements located at different positions.
> The expected result is the minimum number of steps required to obtain a 
> sorted list.
>
> Examples:
> 1 0 1 0 1 -> 1
> 0 1 0 1 1 1 0 -> 2
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.