SoldierLabeling

SRM 446 · 2009-08-08 · by crazyb0y

SRM 446 · 2009-08-08 · by crazyb0y · Math

Show categories

Class Name: SoldierLabeling

Return Type: int

Method Name: count

Arg Types: (int, int, int)

Problem Statement

Tom is a little boy who likes to collect toys. On his birthday, his mom bought him a box of toy soldiers as a gift. There are n soldiers in the box, labeled 1 to n on their uniforms. The numbers are written with no leading zeroes. Tom starts counting the soldiers, but he soon finds that it's difficult to count them all. He decides to count only the soldiers with labels that have length between lowerBound and upperBound, inclusive. Return the number of soldiers that Tom will count.

Constraints

n will be between 1 and 10,000,000, inclusive.
lowerBound will be between 1 and 8, inclusive.
upperBound will be between lowerBound and 8, inclusive.

Examples

100
2
2
Returns: 90

Here there are 100 soldiers and they're labeled 1 to 100. The labels between 10 and 99, inclusive, are of length 2.

31
2
3
Returns: 22

Here there are 31 soldiers and we're looking for labels of length between 2 and 3, inclusive. There are no labels of length 3. Labels between 10 and 31, inclusive, are of length 2.

1
2
8
Returns: 0

Here there is only one soldier and it is labeled 1. We're looking for labels of length between 2 and 8, inclusive, and there are none.

10000000
8
8
Returns: 1

Label 10000000 is the only one here of length 8.

2718317
3
7
Returns: 2718218

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

Coding Area

Language: C++17 · define a public class SoldierLabeling with a public method int count(int n, int lowerBound, int upperBound) · 87 test cases · 2 s / 256 MB per case