Runtime Error LeetCode — 338. Counting Bits in c

Question

The source of question:LeetCode — 338. Counting Bits in c

The introduce: 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.

Example:For num = 5 you should return [0,1,1,2,1,2].

Follow up:

It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?

Space complexity should be O(n).

My code,appear Runtime Error when input 8(sometime 7), the result printf is true:

int* countBits(int num, int* returnSize) {
    *returnSize=num+1;
    int*arr=(int*)malloc(num+1);
    arr[0]=0;
    int i;
    for(i=1;i<num+1;i++){
        arr[i]=arr[i&(i-1)]+1;
        printf("%d\n",arr[i]);
    }
    return arr;
}

Rather than int*arr=(int*)malloc(num+1);, use int* arr = malloc(sizeof *arr * (num+1u)); — chux
– chux, Commented Jul 2, 2016 at 4:13

dbush · Accepted Answer · 2016-07-02 04:13:57Z

1

You're not allocating enough memory. You're currently allocating num+1 bytes, but what you really want is space for num+1 values of type int. So you need to multiply by the size:

int *arr=malloc(sizeof(int)*(num+1));

answered Jul 2, 2016 at 4:13

dbush

233k27 gold badges261 silver badges334 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Runtime Error LeetCode — 338. Counting Bits in c

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related