"Cut the sticks" Python implementation Problem Statement


  You are given N sticks, where the length of each stick is a positive integer. A cut operation is performed on the sticks such that all of them are reduced by the length of the smallest stick.
  
  Suppose we have six sticks of the following lengths:
  
  \$5, 4, 4, 2, 2, 8\$
  
  Then, in one cut operation we make a cut of length 2 from each of the six sticks. For the next cut operation four sticks are left (of non-zero length), whose lengths are the following:
  
  \$3, 2, 2, 6\$
  
  The above step is repeated until no sticks are left.
  
  Given the length of N sticks, print the number of sticks that are left before each subsequent cut operations.
  
  Note: For each cut operation, you have to recalcuate the length of smallest sticks (excluding zero-length sticks).
  
  Input Format
  
  The first line contains a single integer N. 
  The next line contains N integers: \$ a_0, a_1,...a_{N-1}\$ separated by space, where \$a_i\$ represents the length of \$i^\textrm{th}\$ stick.
  
  Output Format
  
  For each operation, print the number of sticks that are cut, on separate lines.
  
  Constraints
  
  $$\begin{align}
1&amp;≤N ≤ 1000,\\
1&amp;≤a_i ≤ 1000,\\
\end{align}$$
  
  Sample Input #00

6
5 4 4 2 2 8

  
  Sample Output #00

6
4
2
1



Solution

def cut_stick(stick, cut_size):
    return stick - cut_size if stick &gt; 0 else stick

def read_ints():
    return map(int, raw_input().strip().split())

def read_int():
    return int(raw_input().strip())

def main(sticks):    
    while not all(x == 0 for x in sticks):
        min_cut_size = min(i for i in sticks if i &gt; 0)
        sticks_cut = len(filter(lambda x: x &gt;= min_cut_size, sticks))
        sticks = map(lambda x: cut_stick(x, min_cut_size), sticks)
        print sticks_cut

if __name__ == '__main__':
    _ = read_int() 
    k = read_ints()
    main(k)


The problem seems too simple I wanted to come up with the solution containing readable code yet efficient at the same time. I am really not satisfied with the given solution (current solution seems \$O(n^2)\$). My basic concern is how to proceed with the proper Data structure and again write some readable code with efficiency at the same time since problems like these appear in the coding competitions most.
You are repeatedly extracting the smallest remaining numbers.  

A data structure that is optimized for such operations is a priority queue, which is typically implemented using a heap.  A heap could be constructed in O(N log N) time, after which you would do N delete-min operations, each of which takes O(log N) time.  The total time to solve this challenge would be O(N log N).

Alternatively, you can sort the numbers in descending order (which takes O(N log N)), then repeatedly pop the smallest numbers off the end of the list (N times O(1)).

So, using a heapq would reduce the running time to O(N log N), and a simple sort would be a more efficient O(N log N).

In fact, after you perform the sort, you will see that it's just a simple counting exercise:

def cuts(sticks):
    sticks = list(reversed(sorted(sticks)))
    i = len(sticks)
    while i:
        # Avoid printing results in your algorithm; yield is more elegant.
        yield i
        shortest = sticks[i - 1]
        while i and sticks[i - 1] == shortest:
            i -= 1

raw_input()    # Discard first line, containing N
for result in cuts(int(s) for s in raw_input().split()):
    print(result)


Here's an implementation of the same idea, but using itertools.groupby to avoid keeping track of array indexes: 

from itertools import groupby

def cuts(sticks):
    sticks = list(sticks)
    sticks_remaining = len(sticks)
    stick_counts_by_len = groupby(sorted(sticks))
    while sticks_remaining:
        yield sticks_remaining
        number_of_shortest_sticks = len(list(next(stick_counts_by_len)[1]))
        sticks_remaining -= number_of_shortest_sticks