3
\$\begingroup\$

https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/

Given a non-negative integer num, return the number of steps to reduce it to zero. If the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.

Example 1:

Input: num = 14 Output: 6 Explanation: Step 1) 14 is even; divide by 2 and obtain 7. Step 2) 7 is odd; subtract 1 and obtain 6. Step 3) 6 is even; divide by 2 and obtain 3. Step 4) 3 is odd; subtract 1 and obtain 2. Step 5) 2 is even; divide by 2 and obtain 1. Step 6) 1 is odd; subtract 1 and obtain 0. Example 2:

Input: num = 8 Output: 4 Explanation: Step 1) 8 is even; divide by 2 and obtain 4. Step 2) 4 is even; divide by 2 and obtain 2. Step 3) 2 is even; divide by 2 and obtain 1. Step 4) 1 is odd; subtract 1 and obtain 0. Example 3:

Input: num = 123 Output: 12

Constraints:

0 <= num <= 10^6

  public int NumberOfSteps (int num) {
        int count = 0;
         while( num !=0)
         {
             if(num %2==0)
             {
                 num = num/2;
                 count++;
             }
             else
             {
                 if( num == 1)
                 {
                     return count+1;
                 }
                 num = num-1;
                 count++;
             }             
         }
         return count;
    }

Please review for performance

\$\endgroup\$
4
\$\begingroup\$

I went a bit crazy about it just for fun, and found a solution that is much more efficient than a loop :)

If you look at the bits as the game progresses, you can reframe the problem. Subtracting 1 from an odd number is flipping the right-most bit from 1 to 0. Dividing by 2 is shifting the bits 1 place to the right.

Example in binary:

1001101

There are four 1-bits, which means 4 subtractions of 1. The left most 1 bit is in the 7th position, which means 6 divisions by 2. There is an exception to this rule when the input is 0, so this is the (almost) final formula:

if (num == 0) return 0;
return (number of 1-bits) + (number of bits to the right of the left-most 1-bit);

A genius SWAR algorithm can be used to count the 1-bits:

public int BitCount(int x)
{
    x -= (x >> 1) & 0x55555555;
    x = ((x >> 2) & 0x33333333) + (x & 0x33333333);
    return (((x >> 4) + x) & 0x0f0f0f0f) * 0x01010101 >> 24;
}

To count the bits on the right of the left-most 1-bit, we can turn them all into 1s by overlapping the number (| operator) with bit shifts of itself:

public int FillGaps(x)
{
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    return x | x >> 16;
}

The final function is:

public int CountSteps_NoLoop(int num)
{
    if(num == 0) return 0;
    return BitCount(num) + BitCount(FillGaps(num)) - 1;
}

There is one more thing that can be done to make the function even faster: because this function is so complicated with lots of bitwise operations, it is slower than a loop for small numbers, so you can do something like this:

public int CountSteps(int num)
{
    const int TIPPING_POINT = 32; // or 16 with Roslyn 3.4 compiler (according to my benchmarks)
    if(num < TIPPING_POINT)
    {
        return CountSteps_Loop(num); // method from my other answer
    }
    else
    {
        return CountSteps_NoLoop(num);
    }
}

Since I already went this far, why not go all the way and avoid function calls and variable declarations (who needs meaningful names):

public int CountSteps(int x)
{
    if(x < 32)
    {
        int c = -1;
        do
        {
            c += 1 + (x & 1);
        } while ( (x >>= 1) != 0);

        return c;
    }
    else
    {
        int s = x - ((x >> 1) & 0x55555555);
        s = ((s >> 2) & 0x33333333) + (s & 0x33333333);

        x |= x >> 1; 
        x |= x >> 2;
        x |= x >> 4;
        x |= x >> 8;
        x |= x >> 16;

        x -= (x >> 1) & 0x55555555;
        x = ((x >> 2) & 0x33333333) + (x & 0x33333333);

        return ((((s >> 4) + s) & 0x0f0f0f0f) * 0x01010101 >> 24)
             + ((((x >> 4) + x) & 0x0f0f0f0f) * 0x01010101 >> 24) - 1;
    }
}

Update: more optimizations!

The main reason I kept the if statement until now is not to speed up the case of 16 smallest numbers, that was just an opportunity to make better use of an if statement that I needed anyway to take care of the case of 0 input. Now I got rid of this if statement and instead of subtracting 1 from the bit count at the end (which created the exception for 0), I shift one bit off of the number before counting the bits (2nd line inside the function). Also according to my benchmarks this shift is faster than subtracting 1 in the end.

I also optimized the return statement by adding both bit counts as early as possible before finishing the count (see the 2nd last line).

public int CountSteps(int x)
{
    int s = x - ((x >> 1) & 0x55555555);
    x = (x >> 1) | (x >> 2);
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x -= (x >> 1) & 0x55555555;
    x = ((x >> 2) & 0x33333333) + (x & 0x33333333)
        + ((s >> 2) & 0x33333333) + (s & 0x33333333);
    return (((x >> 4) & 0x0f0f0f0f) + (x & 0x0f0f0f0f)) * 0x01010101 >> 24;
}

Benchmarking: (with the highest 40 million values of int as function input)

  • code with loop: 3.89s
  • my fancy code: 0.48s
  • with processor instructions: 0.38s

The performance gap will grow if the functions are extended to handle longs, because it's O(1) vs O(n).


Using hardware instructions is the fastest, and makes much clearer code:

public int CountSteps(int x)
{
    return 32 - BitOperations.LeadingZeroCount((uint)x >> 1)
              + BitOperations.PopCount((uint)x);
}

But implementing it without these instructions makes a much more enjoyable challenge.

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

Not much to say for such a simple algorithm. However there is an optimization that you could employ. Check for odd instead of even, then convert to even. Then divide by 2. At most this cuts your iterations by half.

It would look like this:

public int NumberOfSteps(int num)
{
    int count = 0;
    while (num != 0)
    {
        if(num % 2 == 1)
        {
            num -= 1;
            ++count;
        }
        if(num > 0)
        {
            num /= 2;
            ++count;
        }
    }
    return count;
}
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

You need to guard against a negative num, or else your algorithm will run infinitely (num = num - 1).


Dividing 36 and 37 with 2 are both 18 with reminders of 0 and 1. So it should be possible to keep dividing by 2 and adding the reminder, in order to add 1 for odd and 0 for even numbers:

public int Review(int num)
{
  if (num == 0) return 0;

  int result = 0;

  while (num != 0)
  {
    result += 1 + (num & 1);
    num /= 2;
  }

  // The last iteration will always be 1 / 2 which shouldn't be counted.
  result--;

  return result;
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I reviewed your review :) see my answer \$\endgroup\$ – potato Mar 20 at 12:55
  • \$\begingroup\$ @potato: I've seen it - elegant - I have upvoted :-) \$\endgroup\$ – Henrik Hansen Mar 20 at 12:58
2
\$\begingroup\$

My answer is an upgrade of Henrik's answer. (so it's a review of a review lol)

Dividing an int by 2 is the same as shifting the bits 1 to the right. I'd expect a good compiler to make such optimizations automatically, but I think it's still worth mentioning.

I got rid of the if statement at the start, which in most cases (non 0 input) is a waste of time. The do...while removes the need for handling the 0 case differently.

I start the count from -1 to not have to do a subtraction in the end.

Having a do...while loop means one less execution of the while conditional statement, and I also put the bit shift there to not run it more times than necessary.

public int countSteps(int num)
{
   int count = -1;
   do
   {
      count += 1 + (num & 1);
   } while ( (num >>= 1) != 0);
   return count;
}
| improve this answer | |
\$\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.