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 <[email protected]> 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 <[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]. > -- 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 [email protected].
