divisibility for very long number C++

Question

I have given 2 numbers. Lets call them A and B. The number A is very large (which may be in range of -10^20 to 10^20) and the second number B is normal 32 bit integer. So, it is very clear that I can't do it with long long int. I have to determine if A is divisible by B. I tried to put A on a string. But I really don't know how to approach now. I tried this way.

Lets assume

A=1332 and B =3.;

Now sum of the digits of A is = 1+3+3+2 =9.

As 9%3==0 the answer is yes.

But this is not working all the time. I don't know what should I do now.

Can you do it with pen and paper? If so, make the code like that. — Ted Lyngmo, Oct 01 '20 at 08:57
The rule for three should work every time, but you can't use the digit-sum method for all divisors. There are quite a few [special cases](https://en.wikipedia.org/wiki/Divisibility_rule), but there is no general shortcut. — molbdnilo, Oct 01 '20 at 09:07
Hint: `10^(n+1) % B = (10 * (10^n % B)) % B`. This can be used to calculate `A % B` iteratively — Damien, Oct 01 '20 at 09:25
@Damien: True, but that same idea works in all bases. And the question only has one obvious base, namely 2^32. In base 2^32, B is a number with a single digit. You have `unsigned long long`, which is a 2-digit number in base 2^32, but you'll need to have a `vector` for A. — MSalters, Oct 01 '20 at 10:27
@MSalters You are right, but I was not looking for an optimal solution in terms of efficiency. My answer for example works at the digit level, not the fastest one — Damien, Oct 01 '20 at 10:34

score 0 · Answer 1 · answered Oct 01 '20 at 09:34

You have to simply divide one number by another (taking into account special cases laike B==0) and check if remainder is 0. Special rules for 3, 9, 5, 2 will not work in general.

Dividing great number by small number is linear with respect to big number length (digits count).

Take a look at some big numbers library implementations like ones mentioned in the post: How to store extremely large numbers?

score 0 · Answer 2 · answered Oct 01 '20 at 09:44

Consider that A and B are stored in a std::string like: "1234567" and "34".

To divide number stored in string you can just substract B to A in a loop as:

int retained = 0;

// number_cmp return true if A is greater than B
while (number_cmp(A, B)) {
    for (int it = 0; it < B.size(); it++) {
        int a_ = A[it] - '0';
        int b_ = B[it] - '0';
        a_ -= (retained + b);
        if (a_ < 0) { // checking if we need a new reained value;
             retained = 1;
             a_ = 10 + a_;
        } else {
             retained = 0;
        }
        A[it] = a_;
    }
    // here add 1 to a string (if the result of division is huge) or a int for the result
}

If you wan't to opmise the processe you can multiply by 10, 100, 1000,... B if he is very small and you divide a huge number, like:

A = 1.000.000.000
B = 11
--> B = 11 * 1.000.000.0

And when you can no more divide, use the original value or a smaller multiplication value:

A = 1.000.000.000 - (B (110.0000.000) * 9)
A = 10.000.000
--> B = 11 * 100.000
...

Damien · Answer 3 · 2020-10-01T10:36:48.910

One possibility is to simply recursively calculate the remainder of the division by B,
using the property that (100x + 10y + z) % B = 10*((10 * x%B) % B + y)%B + z)%B etc.

The following code assumed A is positive. Handling the negative case is straightforward.

#include <iostream>
#include <string>

bool divisibility (const std::string& A, int B) {
    long long int remainder = 0;
    int n = A.length();
    for (char c: A) {
        int fig = c - '0';
        remainder = (10*remainder + fig) % B;
    }
    //std::cout << "remainder = " << remainder << "\n";
    return remainder == 0;
}

int main() {
    std::string A = "124356925";
    for (int B: {3, 4, 5, 11, 13}) {
        auto ans = divisibility (A, B);
        std::cout << "divisibility of " << A << " by " << B << " is " <<  ans << "\n";
    }
}

score 0 · Answer 4 · answered Oct 01 '20 at 11:01

The straight forward approach is to calculate the cross sum of your long number and check if the cross sum is divisible by 3

#include <string>
#include <iostream>

unsigned int cross_sum ( const std::string & long_int) {
    unsigned int sum = 0;
    for (const auto char_digit:long_int) {
        // converts the char representing the digit to an integer
        const int digit = char_digit - '0'; 
        sum += digit;
        std::cout << sum << " "  << char_digit << " " <<digit <<"\n";
    }
    return sum;
}

int main () {
    std::string long_int = "12345";
    std::cout << cross_sum(long_int) % 3;
}

divisibility for very long number C++

4 Answers4