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

int main() {

      int n;
      scanf("%d",&n);
      int a[n-1];
      for(int i=0;i0&&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

Your code won't work correctly.

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

StackExchange Code Review Q#85669, answer score: 14