September 14th Questions

2009_klees_super_duper_large_array.py

def klees_super_duper_large_array():
    n, k = map(int, input().split())
    """
    # prefix sum appraoch - O(n) time and O(n) space - gives MLE and TLE
    prefix_sum_array = [0] * n
    for i in range(n):
        prefix_sum_array[i] = k
        if i > 0:
            prefix_sum_array[i] += prefix_sum_array[i - 1]

        k += 1

    lowest_x = float("inf")
    for i in range(n):
        left_subarray_sum = prefix_sum_array[i]
        right_subarray_sum = prefix_sum_array[-1] - prefix_sum_array[i]

        lowest_x = min(lowest_x, abs(right_subarray_sum - left_subarray_sum))

    print(lowest_x)
    """

    # def ap_sum(start, end, n):
    #     # print(f"start: {start}; end: {end}; n: {n}")
    #     return (n / 2) * (start + end)

    # left, right = 0, n - 1
    # min_x = float("inf")
    # while left < right:
    #     mid = (left + right) // 2

    #     prefix_sum = ap_sum(k, k + mid, mid + 1)
    #     suffix_sum = ap_sum(k + mid + 1, k + n - 1, n - mid - 1)
    #     # print(
    #     #     f"mid point: {mid}; mid value: {k+mid}; prefix sum: {prefix_sum}; suffix sum: {suffix_sum}"
    #     # )
    #     diff = int(abs(suffix_sum - prefix_sum))

    #     if diff > min_x:
    #         break
    #     min_x = min(min_x, diff)
    #     print(f"difference: {diff}")
    #     left = mid + 1

    # print(min_x)

    # binary search + AP sum approch - log(n) time and O(1) space
    def calculate_sums(mid: int, k: int, n: int):
        # calculate left sum (AP series)
        left_sum = (mid * (k + (k + mid - 1))) // 2
        # calculate right sum (AP series)
        total_sum = (n * (k + (k + n - 1))) // 2
        right_sum = total_sum - left_sum
        return left_sum, right_sum

    left = 1
    right = n
    last_valid_split = 1

    while left <= right:
        mid = (left + right) // 2
        left_sum, right_sum = calculate_sums(mid, k, n)

        if right_sum >= left_sum:
            last_valid_split = mid
            left = mid + 1
        else:
            right = mid - 1

    # check the difference at last_valid_split and last_valid_split + 1
    left_sum1, right_sum1 = calculate_sums(last_valid_split, k, n)
    left_sum2, right_sum2 = calculate_sums(last_valid_split + 1, k, n)

    min_diff = min(right_sum1 - left_sum1, left_sum2 - right_sum2)
    print(min_diff)


t = int(input())
for _ in range(t):
    klees_super_duper_large_array()