C++ sieve instead of brute force


  • 0
    S

    Instead of doing all that dividing, you can use a sieve instead. Basically, I have an array of bitfields where the bitfield at sieve[i] has bit n set if i is divisible by n.

    So the sieve can be set up by iterating over the digits 2 through 9 and then setting the appropriate bits in each of the bitfields. Another trick is that we don't need to keep track of divisibility by 0 or by 1, so there are really only 8 different digits. Conveniently, 8 bits is just the right size to fit into a char instead of having to use a larger integer.

    After creating the sieve of lookups, we can go through the desired numbers and test the digits against the sieve value. A further optimization (that I didn't implement) is handling going through the desired numbers to test without having to do the division by 10 either.

    class Solution {
    public:
        
        vector<int> selfDividingNumbers(int left, int right) {
            vector<int> result;
    
            unsigned char sieve[right+1];
            for (int i=left; i<=right; i++)
                sieve[i] = 0;
            
            for (int digit=2; digit<=9; digit++) {
                unsigned char mask = (1 << (digit-2));
                for (int j=left/digit*digit; j<=right; j+=digit)
                    sieve[j] |= mask;
            }
            for (int i=left; i<=right; i++) {
                int num = i;
                unsigned char sieveBits = sieve[i];
                while (num) {
                    const int newNum = num / 10;
                    const int digit = num - newNum*10;
                    num = newNum;
                    if (digit > 1) {
                        if (((1<<(digit-2)) & sieveBits) == 0)
                            goto NextNum;
                    }
                    else if (digit == 0) {
                        goto NextNum;
                    }
                }
                result.push_back(i);
            NextNum:
                ;
            }
            
            return result;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.