# Cutting The Sticks

Problem Statement

This is a challenge from HackerRank:

You are given N sticks, where each stick has the length of 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 cut in subsequent cut operations.

Input Format

The first line contains a single integer $N$. The next line contains $N$ integers: $a_0, a_1,\ldots, a_{N-1}$ separated by space, where $a_i$ represents the length of $i^{th}$ stick.

Output Format

For each operation, print the number of sticks that are cut in separate line.

Constraints: $1 ≤ N ≤ 1000$ and $1 ≤ a_i ≤ 1000$

Sample Input

6
5 4 4 2 2 8


Sample Output

6
4
2
1


Here is the code

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {

int n;
scanf("%d",&n);
int a[n-1];
for(int i=0;i<n;++i)
{
int stick;
scanf("%d",&stick);
a[i]=stick;
}
int f=0;
do
{
int count=0,small=99;
f=0;
for(int i=0;i<n;++i)
{
if(a[i]>0&&a[i]<small)
small=a[i];
}
for(int i=0;i<n;++i)
{
if(a[i]!=0)
{
a[i]=a[i]-small;
++count;
f=1;
}
}
if(count)
printf("%d\n",count);
}while(f==1);

return 0;
}


How can I improve the above code?

### Variable names

You seem to enjoy short variable names such as a, n, f. These names don't really explain much, especially not the f. a can be named array or data (or even better: sticks), and n can be named length or similar.

### Potential bug

The constraint is 1 ≤ ai ≤ 1000 but you initialize small to 99, which means that if the input is something like:

4
123 123 140 147


### Code Style

It is a good practice to use a bit more spacing than you are using, ittendstohelpswithreadability.

It is also recommended to always use braces, even on one-line statements. Bugs have happened before because of this, only a matter of time before bugs happen again.

For example:

for (int i = 0; i < n; ++i)
{
if (a[i] > 0 && a[i] < small)
{
small = a[i];
}
}


On this line, you can use -= operator:

a[i]=a[i]-small;


Has same effect as:

a[i] -= small;


### Approach

You are looping through the array multiple times and cutting until there are no more elements to cut. This makes your code have worst-case complexity $O(n^2)$ (if all elements would be unique, you would loop $n$ times over $n$ elements, so $n^2$). It is possible to reduce this to $O(n * log(n))$ by sorting the array first, and then looping through it.

For example:

6
5 4 4 2 2 8


If we start by sorting this:

6
2 2 4 4 5 8


And then loop through it:

• We encounter a 2, we know this is the smallest and that the number of elements in the array is 6 so we know we will have to cut 6 sticks. No need to do the actual cutting. Output 6
• We encounter another 2 but this is the same as the previous element so no need to do anything.
• We encounter a 4. This is not equal to 2. We are currently at index 2 so we know that there are $6 - 2 = 4$ elements left in the array. Those elements needs to be cut. Output 4
• Shortly after we encounter the value 5, with only 2 elements left to loop through. So cutting 2 elements. Output 2
• We encounter the 8, only one element left to cut. Output 1