HalvingEasy
SRM 728 · 2018-01-24 · by tourist
Problem Statement
Halving is an operation that takes a nonnegative integer X and transforms it into another nonnegative integer: the value X/2, rounded down if necessary. For example, halving 16 produces 8, and halving 21 gives the result 10.
You are given a
Count the number of elements of S which can be transformed into T by halving them zero or more times. Return this count.
Constraints
- S will contain between 1 and 50 elements, inclusive.
- Each element of S will be between 1 and 109, inclusive.
- T will be between 1 and 109, inclusive.
{6, 14, 11, 3, 1}
3
Returns: 3
6 can be transformed into 3 by halving it once. 14 can be transformed into 3 by halving it twice (14 halved is 7, and 7 halved is 3). 3 can be transformed into 3 by halving it zero times. the other two elements of S (11 and 1) cannot be transformed into 3.
{42, 10, 10, 10, 11, 11, 20, 21, 39, 40, 42, 43, 44}
10
Returns: 9
42, 10, 10, 10, 20, 21, 40, 42 and 43 can be transformed into 10. Note that all occurrences of 10 and 42 are counted towards the answer.
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
1
Returns: 20
Every positive integer can be transformed into 1 by halving zero or more times.
{987654321, 1000000000, 998244353, 123456789, 999999999}
476
Returns: 3
{987654321, 1000000000, 998244353, 123456789, 999999999}
1000000000
Returns: 1
Submissions are judged against all 68 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class HalvingEasy with a public method int count(vector<int> S, int T) · 68 test cases · 2 s / 256 MB per case