Kanade's Perfect Multiples

First, delete duplicate values. Only appearance matters, not frequency. Let $S$ be the set of distinct values in the array.

The tempting wrong read is: this is minimum set cover. That would be ugly. Thankfully, divisibility makes the answer basically forced.

The Forced Values

Call a value $x\in S$ minimal if there is no different value $y\in S$ such that $y\mid x$.

Example: in $S=\{2,3,4,6\}$, the minimal values are $2$ and $3$.

Now observe something important: if $b$ is chosen into $B$, then $b$ must belong to $S$. Why? Rule 2 says every positive multiple of $b$ up to $k$ appears in the array. One of those multiples is $b$ itself. So selected values cannot come from thin air.

Take a minimal value $x\in S$. Rule 1 says some chosen $b\in B$ must divide $x$. But we just proved $b\in S$. Since $x$ has no proper divisor inside $S$, the only possibility is $b=x$.

So every minimal value of $S$ is forced into every valid answer. This is the key. The problem is not asking us to hunt for a clever subset; the subset already walked into the room wearing a name tag.

Why This Is Enough

Let $M$ be the set of minimal values in $S$.

Every valid answer must contain all of $M$, so no valid answer can have size less than $|M|$.

If every value in $M$ satisfies rule 2, then choosing exactly $B=M$ works:

• Rule 2 holds by assumption for every chosen minimal value.
• Rule 1 holds because every $x\in S$ has some minimal divisor from $S$. Start at $x$; if it is not minimal, move to a smaller divisor in $S$; this strictly decreases, so it eventually stops at a minimal divisor.

Therefore:

• If some minimal value fails rule 2, the answer is $-1$.
• Otherwise, the unique minimum-size structure is exactly all minimal values.

Checking Rule 2 Without Enumerating Multiples

For a value $b\in S$, rule 2 says all multiples

$b,2b,3b,\dots,\left\lfloor k/b\right\rfloor b$

appear in $S$.

There are exactly $\left\lfloor k/b\right\rfloor$ such multiples. So rule 2 is equivalent to:

number of distinct values in S divisible by b == floor(k / b)

The left side can never exceed the right side, because all values are between $1$ and $k$. If the count matches, every possible multiple is present. If it is smaller, at least one multiple is missing. Brutally simple.

Computing Minimality and Divisibility Counts

We need two things for each distinct value $v$:

• whether it has a proper divisor also in $S$;
• how many values in $S$ are divisible by $v$.

Do this by iterating over each distinct value $x\in S$, generating all divisors of $x$, and checking which divisors are also in $S$ using a hash map.

For every divisor $d$ of $x$ with $d\in S$:

• increment divCnt[d], because $x$ is divisible by $d$;
• if $d\ne x`, then mark$x$ as non-minimal.

After this pass, the minimal values are exactly the unmarked values. For each one, check divCnt[b] == k / b.

Correctness Proof

Lemma 1. Every selected value $b\in B$ must be in $S$.

Rule 2 requires every positive multiple of $b$ up to $k$ to appear in the array. Since $b$ itself is such a multiple, $b$ appears in the array, so $b\in S$.

Lemma 2. Every minimal value of $S$ must be selected in any complete set.

Let $x\in S$ be minimal. Rule 1 requires some selected $b\in B$ with $b\mid x$. By Lemma 1, $b\in S$. Since $x$ has no proper divisor in $S$, the only possible such $b$ is $x$. Thus $x$ must be selected.

Lemma 3. If all minimal values satisfy rule 2, selecting exactly all minimal values covers every value in $S$.

For any $x\in S$, if $x$ is minimal, it is selected. Otherwise, $x$ has a smaller divisor in $S$. Repeating this process must eventually stop, because the values strictly decrease. The final value is a minimal divisor of $x$, and it is selected. Hence rule 1 holds for $x$.

Lemma 4. For $b\in S$, rule 2 holds iff divCnt[b] == floor(k / b).

There are exactly $\lfloor k/b\rfloor$ positive multiples of $b$ not exceeding $k$. divCnt[b] counts how many of those multiples appear in $S$. Since $S$ contains only values from $1$ to $k$, equality means all multiples appear, and inequality means at least one is missing.

Theorem. The algorithm outputs $-1$ iff no complete set exists; otherwise it outputs a complete set of minimum possible size.

By Lemma 2, every solution must include all minimal values. If any minimal value fails rule 2, no solution can exist. If all pass, Lemma 3 shows the set of all minimal values is complete, and Lemma 2 shows no smaller complete set is possible. So the algorithm is correct.

Complexity

Let $m=|S|$ and let $\tau(x)$ be the number of divisors of $x$.

The main pass does $O\left(\sum_{x\in S}\tau(x)\right)$ hash lookups. Values are at most $10^9$, so divisor counts are small enough for this approach. The solution factors numbers using primes up to $\sqrt{10^9}$ plus a tiny deterministic primality test, so huge prime inputs do not become a modulo-operation crime scene.

Memory usage is $O(m)$.