typedeftemplate's blog

Finding two integers that sum to a target with a constraint
By typedeftemplate, history, 5 years ago, In English

I thought of this problem after encountering a similar problem in TopCoder (many months ago — I can't find the problem anymore; if someone happens to find the problem, please let me know!), and I was wondering whether anyone has an efficient solution to it:

Given an integer N, find two positive integers A and B such that 1) A + B = N

2) Neither A nor B contain a "0" in them.

For example, if N = 12, you could return (7, 5) or (6, 6) or (4, 8), etc. But you wouldn't be able to return (10, 2).

At first thought, I was trying to just set A := N — 1 and B = 1, and decrement/increment A and B until neither had a "0" in them. But for really large cases, something like N = 1099999999999, this can take a really really large time. So then I tried checking each digit and adding 10^(k). But it gets really messy. I was wondering whether there is a nice and efficient solution to this problem, or if the best way is the way I described.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Consider the digits of N one by one, starting from less significant. If you encounter 0, add 10 to this digit, then add 9 to all zeroes between this digit and the next non-zero digit and subtract 1 from this non-zero digit. Do the same if you encounter 1 (if this 1 is not the most significant digit). After this process every digit, except, perhaps, for the most significant one will be in range [2, 11]. The partition then becomes obvious.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks so much for your reply. I am having trouble tracing what you mean.

    For example, let's say you have "2003". Then, we'll start looping, starting from the "1". Since the middle digit is a zero, we add 10 to the digit to get 0 + 10 = 10. So now we have "20103"? And then we add 9 to all zeroes between this digit and the next non-zero digit, so I guess that means we end up with "20103"? I am really not so sure. I would greatly appreciate it if you could please expand a little bit further maybe help me trace one example.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Ok, let me show you the process on the example: 3 | 0 | 0 | 2 -(as 3 > 1)> 3 | 0 | 0 | 2 -> 3 | 10 | 9 | 1 So we have the number with digits 3, 10, 9 and 1. We can now easily make a partition, for example, 1 | 5 | 4 + 2 | 5 | 5 | 1 (the first number consists of $$$[\frac{a[i]}2]$$$). Maybe the wording digit is not so correct, as the values of a[i] are no longer in range [0, 9], the only thing we need is that $$$\sum{a[i] * 10^i} = a$$$

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        Hey, sorry to bother you again. But I think that I actually do not understand, now that I am trying to implement it. Here is what I have tried:

        int main() {
    int N = 2003;
    vector<int> digits_in_N;
    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] += 10;
           i++;
           while (i < reverse_of_int.size(); && reverse_of_int[i] == 0) {
                reverse_of_int += 9; i++;
           }
           if (i < reverse_of_int.size()) reverse_of_int[i] -= 1;
    }
}

        In your first post, you mentioned, "do the same if you encounter 1" but I am not so sure how to add that portion. In addition, I am not sure how to get the numbers A and B. In the partition you said, |1|5|4 + |2|5|5|1, the numbers 154 and 2551 don't add up to N (2003), so I was wondering if you could please clarify.

        Sorry about that.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 4   Vote: I like it 0 Vote: I do not like it

          I use reverse notation for numbers here, $$$a=a[0]+10a[1]+...$$$. In case a[i]=1 you should do literally the same, add 10 to this 1, add 9 to all zeroes after this 1, until you encounter non-zero element. Then subtract 1 from this element. Of course, it may become one or zero, then we'll need to do the same operation once again, starting from this position this time

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            ← Rev. 4   Vote: I like it 0 Vote: I do not like it

            Here is my new code, but it does not currently work for N = 12.

            If N = 12, then we go [2, 1] -> [2, 11], right? Then if we set A := a[i]/2, we'll get A = 15, and B = 16, but 51 + 61 is not equal to 12. Sorry if these questions are really silly to you, I am just trying to learn and get better :) I have been working on this problem all day, and still can't manage to get it to work

            int main() {

	int N = 12;
	vector<int> reverse_of_int;

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

	F0R(i, reverse_of_int.size()) {
		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;


	FORd(i, 0, reverse_of_int.size()) {
		A.push_back(reverse_of_int[i]/2);
	}
	FORd(i, 0, reverse_of_int.size()) {
		B.push_back(reverse_of_int[i] - A[reverse_of_int.size() - 1 - i]);
	}

	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];
	}

	return 0;
}
...
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Please, read my messages carefully, I've written "if it is not the most significant one". Of course, you should not add anything, if all digits after this one are zero

              → Reply