Segmentation Code when inputting higher values

Question

So I created a c++ code that counts "special" numbers in a given range, which is defined as a number where the total of its number of 1-bits in its binary representation is less than our equal to 3 (i.e. 1(1), 2(10), 3(11), 4(100), 5(101), 6(110), 7(111), 8(1000).

I successfully created the code, however there is one problem. At high number ranges, it outputs segmentation fault.

Any idea as to why this happens?

#include <iostream>
#include <cmath>

using namespace std;

long special(long x, long y){
    long sArray[y];
    long output = 0;

    sArray[0]=0;
    sArray[1]=1;

    for(long i = 2; i<=y; i++){
        long j = floor(i/2);
        sArray[i] = sArray[j]+(i%2);
        if (i>=x && sArray[i]<=3){
            output++;
        }
    }
    return output;
}
int main()
{
    cout<<special(5,2717261);
    return 0;
}

`sArray[y]` is out of bounds access. And C++ doesn't allow Variadic Length Arrays. — Yksisarvinen, Oct 20 '18 at 11:44
Why does `special` take two arguments? What are `x` and `y`? — Mureinik, Oct 20 '18 at 11:44
x and y are the ranges where x is the lower bound and y is the higher bound — Samuel Jose, Oct 20 '18 at 11:45
`long sArray[y];` is not legal C++. Learn about `std::vector`. — n. m. could be an AI, Oct 20 '18 at 11:46
c++ doesnt allow variadic length arrays? maybe I should use malloc instead? — Samuel Jose, Oct 20 '18 at 11:47
okay! I got it to work. Thank you everyone for your help. It seems using std::vector solved the problem — Samuel Jose, Oct 20 '18 at 11:54

score 0 · Answer 1 · answered Oct 20 '18 at 11:55

The segmentation fault occurs because you try to declare an array that's too large and extends outside the current memory segment.

Frankly, you don't need this array, and can just count the number of special numbers in the given range:

boolean isSpecial(long num) {
   int bits = 0;
   while (num > 0) {
       if (num % 2 > 0) {
           ++bits;
           if (bits >= 3) {
               return true;
           }
       }
       num /= 2;
   }
   return false;
}

long special(long x, long y) {
    long output = 0;
    for(long i = x; i <= y; ++i) {
        if (isSpecial(i)) {
            ++output;
        }
    }
    return output;
}

Segmentation Code when inputting higher values

1 Answers1