Round Subset · Interview Problem

Back to problems

Codeforces

Hard

Dynamic Programming

Math

Number Theory

Arrays

Google

Round Subset

Choose exactly $k$ numbers to maximize the number of trailing zeros in their product.

Acceptance 0%

Start Practice

Problem Statement

Problem

You are given $n$ integers and an integer $k$ . Choose exactly $k$ of the integers so that the product of the chosen numbers has as many trailing zeros as possible.

A trailing zero is created by a factor of $10 $, and each factor of \$ 10 $comes from one factor of \$ 2 $and one factor of \$ 5$.

Your task is to compute the maximum possible number of trailing zeros in the product of any $k$ selected numbers.

Idea of the task

For each number, count how many times it is divisible by $2 $and by \$ 5 $. Then select a subset of size$ k $that maximizes the minimum of the total number of \$ 2 $s and total number of \$ 5$s in the chosen subset.

Input Format

The first line contains two integers $n$ and $k$ .
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ .

Output Format

Print one integer — the maximum number of trailing zeros in the product of exactly $k$ chosen integers.

Constraints

$1 \le k \le n$
The array contains positive integers
Use 64-bit arithmetic where needed

Note: The exact original contest constraints are not required for practice here.

Examples

Sample cases returned by the problem API.

Example 1

Input

5 3
10 20 25 4 5

Output

Explanation

Choose 10, 20, and 25. Their product is 5000, which has 3 trailing zeros? Let's verify factors: 10 contributes one 2 and one 5, 20 contributes two 2s and one 5, 25 contributes two 5s. Total is 3 twos and 4 fives, so the product has min(3,4)=3 trailing zeros. Therefore the maximum is 3.

Example 2

Input

4 2
2 5 8 25

Output

Explanation

Choosing 8 and 25 gives $8 \cdot 25 = 200$ , which has 2 trailing zeros. No other pair does better.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress