0

This is 338th question of Leetcode,Counting Bits.I think I finish it. But those code get a runtime error when input is 5? but why?

the question is : Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> binaryone(num+1);
        binaryone[0]=0;
        if(0==num)
            return binaryone;
        binaryone[1]=1;
        if(1==num)
            return binaryone;
        int w = 1 ;
        int i = 2;
        while(i<=num+1)
        {
            if(i<(pow(2,w-1)+pow(2,w-2)))
            {
                binaryone[i]=binaryone[i-pow(2,w-2)];
            }
            else
            {
                if(i<=(pow(2,w)-1))
                {
                    binaryone[i]=binaryone[i-pow(2,w-2)]+1;
                }
                else
                {
                    if(i==pow(2,w))
                        {
                            w++;
                            binaryone[i]=binaryone[i-pow(2,w-2)];
                        }
                }
            }
            i++;
        }
        return binaryone;
    }
};
zhaoch93
  • 93
  • 1
  • 10
  • 5
    It sounds like you may need to learn how to use a debugger to step through your code. With a good debugger, you can execute your program line by line and see where it is deviating from what you expect. This is an essential tool if you are going to do any programming. Further reading: **[How to debug small programs](http://ericlippert.com/2014/03/05/how-to-debug-small-programs/)** – NathanOliver Apr 28 '16 at 13:10
  • 1
    your computer is most surely drunk. remove alcohol and try again – aran Apr 28 '16 at 13:11
  • 2
    [Do not use pow() to compute integer powers](http://stackoverflow.com/questions/25678481/why-pown-2-return-24-when-n-5/25678721#25678721) – PaulMcKenzie Apr 28 '16 at 13:18
  • 3
    `pow` is a function for floating-point numbers. You are working with integers and powers of two `2^^n` can be written as `1 << n`. You'll also want to use unsigned ints. – M Oehm Apr 28 '16 at 13:18
  • Also, changing to `at()` instead of using `[ ]` to access the vector elements will more than likely give you a much better error message, since an `out_of_range` exception would be thrown. – PaulMcKenzie Apr 28 '16 at 13:26

1 Answers1

2

I don't think this will hapen only to 5 but to all of your inputs. It is because you created num+1 elements in your binaryone vector by:

vector<int> binaryone(num+1);

and your loop while(i<=num+1) is indexing one past the end of the, zero based indexed, elements giving you a run-time error. If you have n elements, the index range would be from 0 to n-1.

So change your loop condition to: while(i<num+1)

Biruk Abebe
  • 2,235
  • 1
  • 13
  • 24