7
\$\begingroup\$

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?

\$\endgroup\$
14
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.