-1
$\begingroup$

How to solve this problem efficiently?

You are to find all pairs of integers such that their sum is equal to the given integer number N and the second number results from the first one by striking out one of its digits. The first integer always has at least two digits and starts with a non-zero digit. The second integer always has one digit less than the first integer and may start with a zero digit.

Input: A positive integer on a line on its own giving the number of problems. Then, for each problem, single integer N, 10 ≤ N ≤ 10^9. Output: For each problem set, on the first line write the total number of different pairs of integers that satisfy the problem statement. Then, on the following lines, write all those pairs. Write one pair on a line in ascending order of the first integer in the pair. Each pair must be written in the following format: X + Y = N Here X, Y, and N, must be replaced with the corresponding integer numbers. There should be exactly one space on both sides of ’+’ and ’=’ characters.

Example Input:
1
302
Example Output:
5
251 + 51 = 302
275 + 27 = 302
276 + 26 = 302
281 + 21 = 302
301 + 01 = 302

$\endgroup$
  • $\begingroup$ This is my attempt but complexity is very high: gist.github.com/madhur/f6d13ec3d7affa263e22900be4e7b21a $\endgroup$ – Madhur Ahuja Nov 18 '17 at 14:04
  • 1
    $\begingroup$ What's the context where you encountered this problem? Can you credit the source of the problem? Please make sure to cite your sources whenever you copy material from others. $\endgroup$ – D.W. Nov 18 '17 at 18:17
  • $\begingroup$ This is what I found: Problem Author: Vladimir Lelyukh, Roman Elizarov Problem Source: 2001-2002 ACM Northeastern European Regional Programming Contest $\endgroup$ – Madhur Ahuja Nov 19 '17 at 2:58
  • $\begingroup$ acm.timus.ru/problem.aspx?num=1189 $\endgroup$ – Madhur Ahuja Nov 19 '17 at 2:58
  • $\begingroup$ Please don't just leave information in comments. Credit your source in the question. You can click the "edit" button to edit your question and include this information. Also, please indicate all parts that are copied or quoted from another source (in quotations, or using the > sign to mark it as a quote). See cs.stackexchange.com/help/referencing for guidelines. Thank you! $\endgroup$ – D.W. Nov 19 '17 at 5:56
3
$\begingroup$

This answer is but a hint, not a complete solution.

Equivalently, the question is to find natural numbers $a,b,c,p \in \mathbb{N}$ for a given $N \in \mathbb{N}$ such that $$(11a+b) \times 10^p + 2c = N$$ where

  • $0 \leq b < 10$
  • $2c < 10^p$

From this perspective, we can choose how best to iterate our choices. You should derive the possible range of each variable and their relation to each other. To reduce search time, it is recommendable to iterate from the variable that was smaller search range and will limit the range of other variables.

For example, try starting the search by iterating through possible values of $p$ which $0 \leq p \leq \lfloor \log_{10}N \rfloor$

$\endgroup$
3
$\begingroup$

Suppose that the right-hand number results from erasing the $d$th digit from the right (starting to count at 0). We can write the left-hand number as $10^d(10a+b)+c$, where $0 \leq b < 9$ and $c < 10^d$, and then the right-hand number is $10^da+c$. The sum of both numbers is $$ 10^d(10a+b)+c + 10^da+c = 10^d(11a+b)+2c. $$ Given $d$, there are two options for $c$, differing by $5 \cdot 10^{d-1}$. Given $c$, we can calculate $11a+b$, say it needs to be equal to $m$. Then $b \equiv m \pmod{11}$, and this determines $b$ (we might get $b \equiv 10$, in which case we're stuck). Given $b$, we can calculate $a$.

Here is how all of this works out in your case of 302. We know that $0 \leq d \leq 2$, and we proceed to check all options:

  • $d = 0$: then $c = 0$ and $11a+b = 302$, which means that $b \equiv 5 \pmod{11}$, and so $b = 5$. We calculate $a = 27$. The corresponding answer is $275 + 27 = 302$.
  • $d = 1$: then $c=1$ or $c=6$. If $c=1$ then $11a+b = 30$, which means that $b \equiv 8 \pmod{11}$, and so $b = 8$ and $a = 2$. This corresponds to the solution $281 + 21 = 302$. If $c=6$ then $11a+b = 29$, which means that $b \equiv 7 \pmod{11}$, and so $b = 7$ and $a = 2$. This corresponds to the solution $276 + 26 = 302$.
  • $d = 2$: then $c=1$ or $c=51$. If $c=1$ then $11a+b = 3$, which means that $a = 0$ and $b = 3$, corresponding to $301 + 01 = 302$. If $c=51$ then $11a+b=2$, which means that $a = 0$ and $b = 2$, corresponding to $251 + 51 = 302$.

The reasoning above shows that if $N$ is $k$ digits long then there are at most $2k$ solution, and it shouldn't take too much time to sort them.

$\endgroup$
  • $\begingroup$ Can you explain why there are only two options for c? My understanding is that c should be just less than 5*10^(d-1). $\endgroup$ – noman pouigt Nov 19 '17 at 0:56
  • $\begingroup$ Given N there are only two options, since you know most digits of 2c. Take a look at my worked out example. $\endgroup$ – Yuval Filmus Nov 19 '17 at 6:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.