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 <fredericdesmoul...@gmail.com> 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 <rajkuma...@gmail.com> 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 <fredericd...@gmail.com> 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 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.
