Cutting The Sticks

Question

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?

Answer 1

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