Created
September 14, 2024 06:52
-
-
Save AashishNandakumar/63093ce4adbff69b287fa89abea6130e to your computer and use it in GitHub Desktop.
September 14th Questions
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment