Adding time and space complexities. Time complexity: O(n) Space complexity: O(1)
On 29 March 2016 at 23:44, kumar raja <[email protected]> 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 <[email protected]> > wrote: > >> This puzzle comes from a contribution on codingame.com (link to the >> puzzle <https://www.codingame.com/games/community/?puzzleId=103>). 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 [email protected]. >> > > > > -- > 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 [email protected].
