Problem: We have a sequence of N integers: A_1, A_2, \cdots, A_N.  You can perform the following operation between 0 and K times (inclusive):    * Choose two integers i and j such that i \neq j, each between 1 and N (inclusive). Add 1 to A_i and -1 to A_j, possibly producing a negative element.  Compute the maximum possible positive integer that divides every element of A after the operations. Here a positive integer x divides an integer y if and only if there exists an integer z such that y = xz.

Submission attempts (in order):

import sys
import math

def main():
    N, K = [int(i) for i in sys.stdin.readline().strip().split()]
    numbers = [int(i) for i in sys.stdin.readline().strip().split()]
    print(solve(N, K, numbers))


def solve(N, K, numbers):

    total = sum(numbers)
    ans = 1
    candidates = []
    candidates.append(total)
    if total % 2 == 0:
        candidates.append(2)
        candidates.append(total / 2)
    
    # list all possible divisors
    for i in range(3, int(math.ceil(math.sqrt(total)))):
        if total % i != 0:
            continue
        candidates.append(i)
        candidates.append(total/i)
    candidates = [i for i in reversed(candidates)]

    for divisor in candidates:
        need = 1 << 20
        mods = []
        for number in numbers:
            mods.append(number % divisor)
        mods.sort()

        A = 0
        B = 0
        
        for j in range(1, len(mods)):
            A += sum(mods[0:j])
            for k in range(j, len(mods)):
                B += divisor - mods[k]
            need = max(A,B)

            if need < K and A == B:
                ans = max(ans, divisor)
            A = 0
            B = 0   
    return ans


if __name__ == "__main__":
    main()


import sys
import math
INF = 1 << 20

def main():
    N, K = [int(i) for i in sys.stdin.readline().strip().split()]
    numbers = [int(i) for i in sys.stdin.readline().strip().split()]
    print(solve(N, K, numbers))


def solve(N, K, numbers):

    total = sum(numbers)
    ans = 1
    candidates = []
    
    divisor = 1
    # list all possible divisors
    while divisor * divisor <= total:
        if total % divisor == 0:
            candidates.append(divisor)
            candidates.append(total/divisor)
        divisor += 1
    candidates = sorted(candidates, reverse=True)

    for divisor in candidates:
        mods = []
        for number in numbers:
            mods.append(number % divisor)
        mods.sort()
        A = sum(mods)

        need = INF
        index = math.floor(-1 * A/divisor)
        need = sum(mods[0:index])
        if need <= K:
            ans = max(ans, divisor)

    return ans


if __name__ == "__main__":
    main()


import sys
import math
INF = 1 << 20

def main():
    N, K = [int(i) for i in sys.stdin.readline().strip().split()]
    numbers = [int(i) for i in sys.stdin.readline().strip().split()]
    print(solve(N, K, numbers))


def solve(N, K, numbers):

    total = sum(numbers)
    ans = 1
    candidates = []
    
    divisor = 1
    # list all possible divisors
    while divisor * divisor < total:
        if total % divisor == 0:
            candidates.append(divisor)
            candidates.append(total/divisor)
        divisor += 1
    candidates = sorted(candidates, reverse=True)

    for divisor in candidates:
        mods = []
        for number in numbers:
            mods.append(number % divisor)
        mods.sort()
        A = sum(mods)

        need = INF
        index = math.floor(-1 * A/divisor)
        need = sum(mods[0:index])
        if need <= K:
            ans = max(ans, divisor)

    return ans


if __name__ == "__main__":
    main()


import sys
import math
INF = 1 << 20

def main():
    N, K = [int(i) for i in sys.stdin.readline().strip().split()]
    numbers = [int(i) for i in sys.stdin.readline().strip().split()]
    print(solve(N, K, numbers))


def solve(N, K, numbers):

    total = sum(numbers)
    ans = 1
    candidates = []
    
    # list all possible divisors
    for i in range(1, int(math.ceil(math.sqrt(total)))):
        if total % i != 0:
            continue
        candidates.append(i)
        candidates.append(total/i)
    candidates = sorted(candidates, reverse=True)

    for divisor in candidates:
        need = 1 << 20
        mods = []
        for number in numbers:
            mods.append(number % divisor)
        mods.sort()
        A = sum(mods)
        need = INF
        if A % divisor != 0:
            continue
        index = math.floor(-1 * A/divisor)
        need = sum(mods[0:index])
        if need <= K:
            ans = max(ans, divisor)

    return ans


if __name__ == "__main__":
    main()


import sys
import math

def main():
    N, K = [int(i) for i in sys.stdin.readline().strip().split()]
    numbers = [int(i) for i in sys.stdin.readline().strip().split()]
    print(solve(N, K, numbers))


def solve(N, K, numbers):

    total = sum(numbers)
    ans = 1
    candidates = []
    
    # list all possible divisors
    for i in range(1, int(math.ceil(math.sqrt(total)))):
        if total % i != 0:
            continue
        candidates.append(i)
        candidates.append(total/i)
    candidates = [i for i in reversed(candidates)]

    for divisor in candidates:
        need = 1 << 20
        mods = []
        for number in numbers:
            mods.append(number % divisor)
        mods.sort()

        
        A = B = 0
        A = sum(mods)
        for i in reversed(range(len(mods))):
            A -= mods[i]
            B += divisor - mods[i]
            need = min(need, max(A,B))
        if need <= K:
            ans = max(ans, divisor)

    return ans


if __name__ == "__main__":
    main()


import sys
import math
INF = 1 << 20

def main():
    N, K = [int(i) for i in sys.stdin.readline().strip().split()]
    numbers = [int(i) for i in sys.stdin.readline().strip().split()]
    print("%d" % solve(N, K, numbers))


def solve(N, K, numbers):

    total = sum(numbers)
    ans = 1
    candidates = []
    
    divisor = 1
    # list all possible divisors
    while divisor * divisor <= total:
        if total % divisor == 0:
            candidates.append(divisor)
            candidates.append(total/divisor)
        divisor += 1
    candidates = sorted(candidates, reverse=True)

    for divisor in candidates:
        mods = []
        for number in numbers:
            mods.append(number % divisor)
        mods.sort()
        A = sum(mods)

        need = INF
        index = math.floor(-1 * A/divisor)
        need = sum(mods[0:index])
        if need <= K:
            ans = max(ans, divisor)

    return ans


if __name__ == "__main__":
    main()

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted