## Salesforce Record Balancing You're a Salesforc...

Your candidate-prime observation is correct, but factoring every value by all 3,401 primes up to sqrt(10^9) causes the TLE. The solution below adds two improvements:

1. Factor numbers quickly with Miller–Rabin + Pollard–Rho.
2. Use a lower bound to reduce full evaluations to fewer than about 54 primes.

python
import math
from collections import Counter, defaultdict


_SMALL_PRIMES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)


def _is_prime(n):
    if n < 2:
        return False

    for p in _SMALL_PRIMES:
        if n % p == 0:
            return n == p

    # Write n - 1 as d * 2^s.
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1

    # Deterministic for the range used by this problem.
    for a in (2, 3, 5, 7, 11):
        if a >= n:
            continue

        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue

        for _ in range(s - 1):
            x = x * x % n
            if x == n - 1:
                break
        else:
            return False

    return True


def _pollard_rho(n):
    if n % 2 == 0:
        return 2
    if n % 3 == 0:
        return 3
    if n % 5 == 0:
        return 5

    c = 1

    while True:
        # Brent's version of Pollard-Rho.
        y = 2
        r = 1
        q = 1
        g = 1
        block_size = 64

        while g == 1:
            x = y

            for _ in range(r):
                y = (y * y + c) % n

            k = 0

            while k < r and g == 1:
                ys = y
                steps = min(block_size, r - k)

                for _ in range(steps):
                    y = (y * y + c) % n
                    q = q * abs(x - y) % n

                g = math.gcd(q, n)
                k += steps

            r *= 2

        if g == n:
            while True:
                ys = (ys * ys + c) % n
                g = math.gcd(abs(x - ys), n)

                if g > 1:
                    break

        if g != n:
            return g

        c += 1


def _collect_prime_factors(n, result):
    if n == 1:
        return

    if _is_prime(n):
        result.add(n)
        return

    divisor = _pollard_rho(n)
    _collect_prime_factors(divisor, result)
    _collect_prime_factors(n // divisor, result)


def getMinimumRecords(recordCounts):
    n = len(recordCounts)
    frequency = Counter(recordCounts)

    # k = 2 always gives cost equal to the number of odd values.
    answer = sum(
        count
        for value, count in frequency.items()
        if value % 2 == 1
    )

    if answer == 0:
        return 0

    factor_cache = {}

    def factors(value):
        if value < 2:
            return ()

        cached = factor_cache.get(value)
        if cached is not None:
            return cached

        result = set()
        _collect_prime_factors(value, result)

        result = tuple(result)
        factor_cache[value] = result
        return result

    # divisible[p] = number of original values divisible by p.
    divisible = defaultdict(int)
    original_factors = {}

    for value, count in frequency.items():
        current = factors(value)
        original_factors[value] = current

        for p in current:
            divisible[p] += count

    # near[p] = number of values whose distance from a multiple
    # of p is at most 1.
    near = defaultdict(int)

    for value, count in frequency.items():
        if value == 1:
            # 1 is distance 1 from zero for every p.
            continue

        candidate_factors = set(original_factors[value])
        candidate_factors.update(factors(value - 1))
        candidate_factors.update(factors(value + 1))

        for p in candidate_factors:
            if p in divisible:
                near[p] += count

    ones = frequency.get(1, 0)

    if ones:
        for p in divisible:
            near[p] += ones

    candidates = []

    for p, zero_cost_count in divisible.items():
        if p == 2:
            continue

        near_count = near[p]

        # Values divisible by p cost 0.
        # Other near values cost 1.
        # Values not near a multiple cost at least 2.
        lower_bound = (
            near_count - zero_cost_count
            + 2 * (n - near_count)
        )

        if lower_bound < answer:
            candidates.append(p)

    # Process common values first so candidates often terminate earlier.
    values = sorted(
        frequency.items(),
        key=lambda item: item[1],
        reverse=True
    )

    for p in candidates:
        current_cost = 0

        for value, count in values:
            remainder = value % p
            distance = min(remainder, p - remainder)

            current_cost += distance * count

            if current_cost >= answer:
                break

        if current_cost < answer:
            answer = current_cost

    return answer

Why only prime values of k matter

If k is composite and p is one of its prime factors, every multiple of k is also a multiple of p. Therefore, moving a number to a multiple of p can never cost more than moving it to a multiple of k.

So some optimal answer always uses a prime k.

Also, if a prime divides none of the input values, every value costs at least one modification. Its total is therefore at least n, while k = 2 always costs at most n. Such a prime cannot improve the answer.

The pruning bound

For a candidate prime p, define:

• z: number of values divisible by p
• t: number of values where one of x - 1, x, or x + 1 is divisible by p

Then:

• z values cost 0
• t - z values cost 1
• n - t values cost at least 2

Therefore:

text
cost(p) >= (t - z) + 2(n - t)
        = 2n - t - z

Only candidates whose lower bound beats the current answer are evaluated fully.

Each number among x - 1, x, and x + 1 has at most nine distinct prime factors in the given range. Consequently, fewer than roughly 54 primes can pass the heavy-candidate test, making the final scanning phase effectively linear.

The sample results are:

text
[4, 7, 5, 11, 15] -> 4
[3, 8, 7, 6, 4]   -> 2
[3, 9, 7, 6, 5, 2] -> 3