Re: [algogeeks] Minimal number of swaps

[ranganath g]

Thanks!

-- 
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.

Re: [algogeeks] Minimal number of swaps

[tec]

It's essentially the same as kumar's algorithm.
a[n - 1] records the total number of 1's, ie. K;
a[a[n-1]-1] = a[K-1] records the number of 1's in the first K elements.
the difference K-a[K-1] is the number of 0's in the first K elements, to be
swapped for remaining 1's.

2016-04-19 16:54 GMT+08:00 ranganath g :

> Hey Sachin,
>
> What is the correctness of your code? I mean how do you say that this is
> give the right answer
>
> --
> 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.
>



-- 
__

-- 
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.

Re: [algogeeks] Minimal number of swaps

[ranganath g]

Hey Sachin,

What is the correctness of your code? I mean how do you say that this is
give the right answer

-- 
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.

Re: [algogeeks] Minimal number of swaps

[Shachindra A C]

1 - keep a running total of the sum in an array (or reuse the same array)
2 -  a[n - 1] (ie, the length of the array) - a[a[n - 1] - 1] is the answer

0 1 0 1 1 1 0
0 1 1 2 3 4 4

ans  = 4 - a [ 4 - 1 ] = 2


1 0 1 0 1
1 1 2 2 3

ans  = 3 - a [ 3 - 1 ] = 1

Same Os as the prev solution mentioned, except that the second pass isnt
required.




On Tue, Mar 29, 2016 at 12:29 PM, Régis Bacra 
wrote:

> Clever. Thanks!
>
> Le mardi 29 mars 2016 20:23:22 UTC+2, kumar raja a écrit :
>>
>> Adding time and space complexities.
>>
>> Time complexity: O(n)
>> Space complexity: O(1)
>>
>>
>> On 29 March 2016 at 23:44, kumar raja  wrote:
>>
>>> I think it is straight forward. Correct me if i am wrong or if there is
>>> better solution.
>>>
>>> 1) Do one pass over the list of elements and count the number of 1's.
>>> let us say it is K
>>> 2)  count = 0
>>>   from index 0 to K-1 do
>>>  if array[index] != 1
>>> count ++
>>>  end
>>>   end
>>>
>>> The variable "count"  indicates the minimum number of steps required to
>>> obtain a sorted list.
>>>
>>>
>>> On 29 March 2016 at 19:30, 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+...@googlegroups.com.

>>>
>>>
>>>
>>> --
>>> Regards
>>> Kumar Raja
>>>
>>>
>>>
>>
>>
>> --
>> Regards
>> Kumar Raja
>>
>>
>> --
> 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.
>



-- 
Regards,
Shachindra A C

-- 
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.

Re: [algogeeks] Minimal number of swaps

[Régis Bacra]

Clever. Thanks!

Le mardi 29 mars 2016 20:23:22 UTC+2, kumar raja a écrit :
>
> Adding time and space complexities.
>
> Time complexity: O(n)
> Space complexity: O(1)
>
>
> On 29 March 2016 at 23:44, kumar raja  
> wrote:
>
>> I think it is straight forward. Correct me if i am wrong or if there is 
>> better solution.
>>
>> 1) Do one pass over the list of elements and count the number of 1's. let 
>> us say it is K
>> 2)  count = 0
>>   from index 0 to K-1 do
>>  if array[index] != 1
>> count ++
>>  end
>>   end
>>
>> The variable "count"  indicates the minimum number of steps required to 
>> obtain a sorted list.
>>
>>
>> On 29 March 2016 at 19:30, 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+...@googlegroups.com .
>>>
>>
>>
>>
>> -- 
>> Regards
>> Kumar Raja
>>
>>
>>
>
>
> -- 
> Regards
> Kumar Raja
>
>
>

-- 
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.

Re: [algogeeks] Minimal number of swaps

[kumar raja]

Adding time and space complexities.

Time complexity: O(n)
Space complexity: O(1)


On 29 March 2016 at 23:44, kumar raja  wrote:

> I think it is straight forward. Correct me if i am wrong or if there is
> better solution.
>
> 1) Do one pass over the list of elements and count the number of 1's. let
> us say it is K
> 2)  count = 0
>   from index 0 to K-1 do
>  if array[index] != 1
> count ++
>  end
>   end
>
> The variable "count"  indicates the minimum number of steps required to
> obtain a sorted list.
>
>
> On 29 March 2016 at 19:30, 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.
>>
>
>
>
> --
> Regards
> Kumar Raja
>
>
>


-- 
Regards
Kumar Raja

-- 
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.

Re: [algogeeks] Minimal number of swaps

[kumar raja]

I think it is straight forward. Correct me if i am wrong or if there is
better solution.

1) Do one pass over the list of elements and count the number of 1's. let
us say it is K
2)  count = 0
  from index 0 to K-1 do
 if array[index] != 1
count ++
 end
  end

The variable "count"  indicates the minimum number of steps required to
obtain a sorted list.


On 29 March 2016 at 19:30, 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.
>



-- 
Regards
Kumar Raja

-- 
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] Minimal number of swaps

[Régis Bacra]

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.