ChildlessNumbers

SRM 473 · 2009-11-12 · by misof

SRM 473 · 2009-11-12 · by misof · Brute Force, Math, Simple Search, Iteration

Show categories

Class Name: ChildlessNumbers

Return Type: int

Method Name: howMany

Arg Types: (int, int)

Problem Statement

Let D(X) denote the sum of digits of the positive integer X. For example, D(4007) = 4 + 0 + 0 + 7 = 11.

Take any positive integer X, and let Y = X / D(X). If Y is an integer, we say that Y is the parent of X (and that X is a child of Y). For example, if X=12 then X / D(X) = 12 / (1+2) = 4, hence 4 is the parent of 12.

Note that multiple numbers can have the same parent. For example, 4 is also the parent of 36, as 36/(3+6) = 36/9 = 4.

We say that a number Y is childless if there is no positive integer X such that Y is the parent of X.

You are given two ints A and B. Find and return the count of all childless numbers that lie between A and B, inclusive.

Constraints

A will be between 1 and 1,000,000,000, inclusive.
B will be between A and 1,000,000,000, inclusive.
B-A will be between 0 and 10,000, inclusive.

Examples

4
7
Returns: 0

Each of the numbers {4,5,6,7} has at least one child. For example, 54 / (5+4) = 6, hence 6 is not childless.

37
37
Returns: 0

E.g., 333 / (3+3+3) = 37.

61
65
Returns: 3

In this range there are three childless numbers: 62, 63, and 65. For the other two we have 732 / (7+3+2) = 732/12 = 61 and 320 / (3+2+0) = 320/5 = 64.

275
300
Returns: 1

The only childless number in this range is 276.

999990000
1000000000
Returns: 1950

246889265
246899265
Returns: 6714

Largest possible output.

112)

966660000
966670000
Returns: 971

Requires checking sum of at least 93

Submissions are judged against all 127 archived test cases, of which 7 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ChildlessNumbers with a public method int howMany(int A, int B) · 127 test cases · 2 s / 256 MB per case