Problem
Let's say that number
a
feels comfortable with number b
if a ≠ b
and b
lies in the segment [a - s(a), a + s(a)]
, where s(x)
is the sum of x
's digits.
How many pairs
(a, b)
are there, such that a < b
, both a
and b
lie on the segment [L, R]
, and each number feels comfortable with the other?
Example
For
L = 10
and R = 12
, the output should becomfortableNumbers(L, R) = 2
.
Here are all values of
s(x)
to consider:s(10) = 1
, so10
is comfortable with9
and11
;s(11) = 2
, so11
is comfortable with9
,10
,12
and13
;s(12) = 3
, so12
is comfortable with9
,10
,11
,13
,14
and15
.
Thus, there are
2
pairs of numbers comfortable with each other within the segment [10; 12]
: (10, 11)
and (11, 12)
.
Input/Output
- [time limit] 500ms (cpp)
- [input] integer LGuaranteed constraints:
1 ≤ L ≤ R ≤ 1000
. - [input] integer RGuaranteed constraints:
1 ≤ L ≤ R ≤ 1000
. - [output] integerThe number of pairs satisfying all the above conditions.
Solution
The problem is pretty straightforward due to constraints of the problem. We need to look at 1000C2 pairs in the worst case. We look at all the pairs in the range [L, R] and check if the pair of integers in a given pair are comfortable to each other.
Code
int digitSum(int n){ int _sum = 0; while (n){ _sum += (n%10); n = n/10; } return _sum; } int comfortableNumbers(int L, int R) { int total_pairs = 0; for(int i=L; i<=R; i++){ for(int j=i+1; j<=R; j++){ int s_a = digitSum(i); int s_b = digitSum(j); if (j>= (i-s_a) and j<= (i+s_a) and i>= (j-s_b) and i<= (j+s_b) ) { total_pairs++; } } } return total_pairs; }