samedi 28 septembre 2019

Finding two integers that sum to a target integer

This is a problem that from an algorithmic challenges book that I have been struggling with for the past couple days.

Given an integer N, find two positive integers A and B such that A + B = N and neither A nor B contain a "0" in them. For example, if N = 12, you would be able to return (A, B) = (6, 6), (5, 7), (4, 8), (3, 9), etc but you wouldn't be able to return (10, 2) or (2, 10).

I have been struggling to solve this problem for several days, and I cannot understand a solution that someone else gave me. I was wondering whether someone would either be able to make sense of the solution and help me implement it, or if they are able to come up with an (efficient) solution of their own.

Here is the solution that I was told:

"Consider the digits of N one-by-one, starting from the least significant digit. If you encounter the number 0, add 10 to the digit, and add 9 to all zeroes between this digit and the next non-zero digit, and subtract 1 from this non-zero digit. Of course, this non-zero digit might become zero, and if this is the case, we need to do the same thing, starting from this index. Also, you should do the same thing if you encounter a 1 (as long as this 1 is not the most significant digit). Afterwards, process every digit, except perhaps, for the most significant one will be in range [2, 11], a partition will become obvious.

As an example, suppose we have 2003. Then, we process it in reverse to get 3002 -> 3 | 10 | 9 | 1, so we have the digits 3, 10, 9, and 1. From here, we can can easily make a partition, for example, 1|5|4 and |2|5|5|1 (the first number consists of A[i]/2), and we can see that 451 + 1552 = 2003."


I'm really confused about how to implement what they're talking about. I've tried my best for the past several hours with no luck. I was hoping someone here would either know a good solution to solve this problem, or if they are able to make sense of the solution provided above (either one is fine). Here is what I've tried to implement in C++; however, it does not actually work for all numbers (e.g. it breaks for N = 12, N = 13, and several other examples).

int main() {

    int N = 2003;
    vector<int> reverse_of_int;

    while (N > 0) {
        reverse_of_int.push_back(N % 10);
        N /= 10;
    }

    for (int i = 0; i < reverse_of_int.size(); i++) {
        if (reverse_of_int[i] == 0 || reverse_of_int[i] == 1) {
            reverse_of_int[i] += 10;
            i++;
            while (i < reverse_of_int.size() && reverse_of_int[i] == 0) {
                reverse_of_int[i] += 9;
                i++;
            }
            if (i < reverse_of_int.size()) {
                reverse_of_int[i] -= 1;
            }
        }

        if ((reverse_of_int[i] == 0 || reverse_of_int[i] == 1) && i != reverse_of_int.size() - 1) {
            i--;
        }
    }

    vector<int> A;
    vector<int> B;


    for (int i = reverse_of_int.size() - 1; i >= 0; i--) {
        A.push_back(reverse_of_int[i]/2);
        B.push_back(reverse_of_int[i] - A[reverse_of_int.size() - 1 - i]);
    }


    cout << "ANSWER for N =  " << copyN << endl;
    bool flag = false;
    F0R(i, A.size()) {
        if (A[i] == 0 && i != 0) flag = true;
        cout << A[i];
    }
    cout << endl;
    F0R(i, B.size()) {
        if (B[i] == 0 && i != 0) flag = true;
        cout << B[i];
    }
    cout << endl;

    return 0;
}

Aucun commentaire:

Enregistrer un commentaire