# "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

return map(int, raw_input().strip().split())

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__':
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

• Reminding that 0 is not the minimum here hence I need to keep checking that too. Commented Oct 6, 2015 at 8:26
• Can you please explain a more about that cumulative length stuff? Commented Oct 6, 2015 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. Commented Oct 6, 2015 at 19:37
• For 1st solution the solution is still \$O(n^2)$\ I think. But very clever trick indeed. Commented Oct 8, 2015 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. Commented Oct 8, 2015 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) Commented Oct 18, 2015 at 18:37
• And your solution might even be faster than @200_success, because the sorted is done on a (possibly) smaller list Commented Oct 18, 2015 at 18:39

This solution uses more memory, but it's quite intuitive as opposed to some of the bulkier approaches.

First, it identifies the unique sticks in the array. It creates a corresponding dictionary storing the stick's length, and the number of sticks with this length. Each unique stick is appended to a list on unique sticks, seen as keys below.

Then, the keys are sorted by stick length, to ensure that we remove sticks with the smallest length first. We append the number of sticks we currently have to the list we will return, sticks_remaining.

At first, all sticks will remain, and thus we will return N, or the length of the input array. Then, as we iterate through unique sticks, we will remove d[stick_length], as to remove all duplicates of the stick of the current length. We will do this for all the unique keys, and yield the amount of sticks left until we have passed through all keys.

This solution is better primarily for readability and running faster than the primary solution given above.

def solve(seq):
d = {}
keys = sticks_cut = []
N = sticks_remaining = len(seq)

for stick in seq:
if stick not in d:
d[stick] = 1
keys.append(stick)
else:
d[stick] += 1
keys.sort() # Ensures that we will look at the smallest sticks first

for key in keys:
yield sticks_remaining
sticks_remaining -= d[key] # Removes the number of sticks 'key' there are