DivideByZero
SRM 610 · 2013-12-22 · by rng_58
Problem Statement
Little John has a piece of paper with some distinct integers written on it.
You are given a
John is now going to add some new numbers to his paper. While doing so, he will be using integer division. When doing integer division, we discard the fractional part of the result. In this problem, we will use "div" to denote integer division. For example, 15 div 5 = 3, and 24 div 5 = 4.
John will repeat the following process: He will look at his paper and select two distinct numbers A and B such that A is greater than B. He will compute C = A div B. If C is not written on his paper yet, he will add it to the paper.
The process will stop once there is no way for John to add a new number to his paper. Compute and return how many numbers will there be on John's paper at the end.
Notes
- The return value does not depend on the order in which John adds new numbers to his paper.
Constraints
- numbers will contain between 1 and 100 elements, inclusive.
- Each element of numbers will be between 1 and 100, inclusive.
- The elements in numbers will be distinct.
{9, 2}
Returns: 3
John starts with just 9 and 2 on his paper. He can add the number 4, because 9 div 2 = 4. After he adds the number 4, there will be no more numbers to add, because 9 div 4 = 2, and also 4 div 2 = 2. Thus, at the end John's paper will contain 3 numbers: 9, 2, and 4.
{8, 2}
Returns: 3
{50}
Returns: 1
We only have one number. There isn't anything John can do.
{1, 5, 8, 30, 15, 4}
Returns: 11
{1, 2, 4, 8, 16, 32, 64}
Returns: 7
{6, 2, 18}
Returns: 7
Once John has a number on his paper, he can use it when producing new numbers. For example, in this case he can add 9 (computed as 18 div 2), and then add 1 (computed as 9 div 6). The numbers he will have at the end are 1, 2, 3, 4, 6, 9, and 18.
Submissions are judged against all 133 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DivideByZero with a public method int CountNumbers(vector<int> numbers) · 133 test cases · 2 s / 256 MB per case