Next multiple with only 1 and 0 as digit

Question

Problem: Find a multiple of a given decimal number \$N\$ that looks like a binary number.

The input will consist of at most \$ 2 \times 10^5 \$ lines, each line consist of an integer \$N\$ (\$0 \lt N \lt 10^{12} \$). Find its described multiple \$M (\ne 0\$), this number \$M\$ must be less than \$10^{12}\$. If there is no such number, print '\$-1\$' on the output.

My solution to this problem is quite simple. Just generated all binary-like numbers less than \$10^{12}\$ excluding \$0\$ (there are \$4095\$ such numbers).

For each number from input, just do a linear search on the binary numbers list. Is it possible to do it faster?

#include <cstdio>
#include <vector>

std::vector<long long> bits;

void generateBits(){

    for (int i = 1; i < 4096; ++i) {

        long long e = 1; //e is the exponencial of 10
        long long n = i; //n will be used to extract the bits from the number i
        long long d = 0;//binary-like decimal number...

        while (n) {
            d += ((n&1)*e);
            n >>= 1, e *= 10;
        }

        bits.push_back(d);
    }
}

long long getBitMultiple(long long n){

    for (auto &bit : bits) {
        if(bit%n == 0){
            return bit;
        }
    }

    return -1;
}

int main(void){

    generateBits();

    long long n;

    while (scanf("%lld",&n) != EOF) {
        printf("%lld\n",getBitMultiple(n));
    }

    return 0;
}

Answer 1

I normally don't do C++ reviews, so I might be off on a few accounts, but here are some style and code review points.

Style and Code Review

• Avoid cramped up statements – Mostly your code reads easily, but avoid stuff like if(bit%n == 0){, open it up to become if (bit % n == 0) {. Especially important since you seem to have decided on having the starting brace on the same line. It needs to stand out to be recognised. Along the same line of reasoning, add a space after commas like in the printf("...", getBitMultiple(n));
• Aim for better names – Names like e, n and d are not really intuitive. Neither is bit or getBitMultiple, it is not a bit but a decimal number looking like a binary. Confusing. Maybe change bits into binaryLookingDecimals?
• Add more comments – Parts of the code is unclear, like what you are aiming for in your functions, and where do you get your numbers from, and how does your while loop work
• Avoid using globals – The main table of your code, bits, is a global variables. As it reads now, the generateBits() and getBitMultiple(n) are separate non-related functions. If however you add something like binaryLookingDecimals = generateBinaryLookingDecimals() and findMultiple(n, binaryLookingDecimals) they are clearly related

Edited: My solution review was based on a misunderstanding of the problem statement. As a foreigner I confused multiple/multiply/multiplicand, and thought you had done the same. Your code does however return the binary looking decimal which is a multiple of \$N\$ as requested, and that renders my previous solution void, which found the factor you need to multiply to \$N\$ to get a binary looking decimal.

The only comment I then have to your actual solution, is whether it is worth it to test whether the candidate is greater than \$N\$ before starting the modulo operation, but that has to be tested if it gives any significant speed increase. Most likely it is not worth it.

_{Thanks to Barry for correcting me regarding my mistake on the solution review}

Answer 2

Here is an alternate version for finding the multiple of \$N\$ which looks like a binary. It doesn't depend on a prebuilt table of binary looking decimals, but generates these on the fly. This is done using a counter from 1 through 4096, which is converted to a binary string¹, before that binary string is converted back to a long long. This newly formed binary looking decimal is then used in the modulo operator testing.

findBinaryLookingDecimal(long long n) {
    std::string iAsBinary; // Holds the binary version of i, i.e. i=5 -> 101
    long long binaryLookingDecimal; // The string converted to long, i.e. 0b101 = 0l101

    for (i = 1; i < 4096; i++) {
        iAsBinary = std::bitset<std::numeric_limits<unsigned long long>::digits>(i).to_string();
        // or possibly use std::bitset< 64 >( i ).to_string()

        binaryLookingDecimal = std::stoll(iAsBinary); // Back to a long long

        if (binaryAsLongLong % n == 0) {
            return binaryLookingDecimal;
    }
    return -1;
}

The advantage of this version, is that it doesn't depend on a prebuilt table, which also is it's disadvantage if you are going to test this for a large number of \$N\$'s. Another benefit is that it only calculates as many binary looking decimal as needed, which for \$N = 97\$ would make the loop go until \$i=225\$, before returning the result: "11100001". That is saving over 3800 iterations of precalculations in that particular case.

It also displays a different version on how to find all the binary looking decimals, and if so wanted can be a replacement for the calculations used in generateBits() with a few slight modifications. As the code is untested, I will not claim it to be faster or slower. But the memory footprint, should at least be smaller.

_{¹ Conversion to a binary string based on a variation of this answer}

Answer 3

The table generation can certainly be simpler and faster by removing the direct binary-to-decimal conversion:

void generateBits(){
    long long d = 1;
    bits.push_back(d);
    for (int i = 0; d < 11111111111L; ++i) {
        d = bits[i];
        bits.push_back(d * 10);
        bits.push_back(d * 10 + 1);
    }
}

(Of course, this has a hideous magic number, but it's not much worse than the 4096 in the one it replaces).

Answer 4

Yes, you can do it faster, in \$O(max(N, c))\$ where \$c\$ is the number of binary-like numbers under the specified limit, using breadth-first search.

The vertices are values mod \$N\$. There is an edge from \$x\$ to \$y\$ iff \$10x = y\$ or \$10x+1 = y\$. Starting at \$0\$, and when you get \$0\$ again, the sequence of the choices between the two equations is an answer.