Finding two integers that sum to a target with a constraint

Блог пользователя typedeftemplate

Автор typedeftemplate, история, 7 лет назад, По-английски

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.

#array

typedeftemplate
7 лет назад
10

Комментарии (7)

Показать архивные | Написать комментарий?

SendThemToHell

7 лет назад, скрыть # |

← Rev. 2 →

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.

→ Ответить

typedeftemplate

7 лет назад, скрыть # ^ |

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.

→ Ответить

SendThemToHell

7 лет назад, скрыть # ^ |

← Rev. 3 →

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$$$

→ Ответить

typedeftemplate

7 лет назад, скрыть # ^ |

← Rev. 3 →

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.

→ Ответить

SendThemToHell

7 лет назад, скрыть # ^ |

← Rev. 4 →

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

→ Ответить

typedeftemplate

7 лет назад, скрыть # ^ |

← Rev. 4 →

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

→ Ответить

SendThemToHell

7 лет назад, скрыть # ^ |

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

→ Ответить