PermutationAndMultiplication | Topcoder Archive

Problem Statement

You are given two ints: ones and zeroes. You need to do the following:

Let A be the largest integer whose binary representation consists of exactly ones 1s and zeroes 0s.
Let B be the smallest integer whose binary representation consists of exactly ones 1s and zeroes 0s.
Let C = A*B.

Compute and return the number of 1s in the binary representation of C.

Definition

Class:: PermutationAndMultiplication
Method:: multiplyAndCount
Parameters:: int, int
Returns:: int
Method signature:: int multiplyAndCount(int ones, int zeroes)
(be sure your method is public)

Notes

The binary representations of A and B are not allowed to have leading zeroes.

Constraints

ones will be between 1 and 200,000, inclusive
zeroes will be between 0 and 200,000, inclusive

Examples

```
2
```
```
2
```
```
Returns: 4
```
A = 12 (in decimal) = 1100 (in binary) B = 9 (in decimal) = 1001 (in binary) Thus, A*B = 108 (in decimal) = 1101100 (in binary). The number 1101100 contains four 1s, so the correct answer is 4.
```
1
```
```
2
```
```
Returns: 1
```
Here we have A = B = 4, and thus A*B = 16. (In binary, A = B = 100 and A*B = 10000.)
```
2
```
```
0
```
```
Returns: 2
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.