HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

Next multiple with only 1 and 0 as digit

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
withnextmultipleanddigitonly

Problem

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 
#include 

std::vector bits;

void generateBits(){

    for (int i = 1; i >= 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;
}

Solution

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

Context

StackExchange Code Review Q#107221, answer score: 3

Revisions (0)

No revisions yet.