# “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&≤N ≤ 1000,\\ 1&≤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 > 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 > 0)
sticks_cut = len(filter(lambda x: x >= 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.

## 2 Answers

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)))
sticks_remaining -= number_of_shortest_sticks

• Reminding that 0 is not the minimum here hence I need to keep checking that too. – CodeYogi Oct 6 '15 at 8:26
• Can you please explain a more about that cumulative length stuff? – CodeYogi Oct 6 '15 at 17:25
• Never mind about the cumulative length. The lengths themselves are actually irrelevant. What matters is the count of sticks of each length. – 200_success Oct 6 '15 at 19:37
• For 1st solution the solution is still \$O(n^2)$\ I think. But very clever trick indeed. – CodeYogi Oct 8 '15 at 4:42
• That's one way to look at it. The rigorous explanation is that if i starts at n and ends at 0, then i -= 1 must get executed exactly n times. – 200_success Oct 8 '15 at 7:45

This a one-liner (well, a two-liner to keep it in 80 columns) using collections.Counter and itertools.accumulate:

from collections import Counter
from itertools import accumulate

def sticks_remaining(sticks):
"""Return list giving number of sticks remaining before each operation
(in which all sticks are reduced by the length of the shortest
remaining stick).

>>> list(sticks_remaining([5, 4, 4, 2, 2, 8]))
[6, 4, 2, 1]

"""
c = sorted(Counter(sticks).items(), reverse=True)
return reversed(list(accumulate(v for _, v in c)))

• That's quite nice, but some more comments about your two lines would help more people to grasp its beauty ;-) For instance with comments explaining how the example list is treated (notably after Counter) – oliverpool Oct 18 '15 at 18:37
• And your solution might even be faster than @200_success, because the sorted is done on a (possibly) smaller list – oliverpool Oct 18 '15 at 18:39