I’m trying to solve this Problem from GFG with following approach:
class Solution: def getMinDiff(self, arr, n, k): # code here arr.sort() min_diff = arr[-1] - arr if min_diff <= k: return min_diff min_ele = arr + k max_ele = arr[-1] - k if min_ele > max_ele: min_ele, max_ele = max_ele, min_ele for i in range(1, n-1): curr_min = arr[i] - k curr_max = arr[i] + k if curr_min >= min_ele or curr_max <= max_ele: continue if max_ele - curr_min <= curr_max - min_ele: min_ele = curr_min else: max_ele = curr_max return min(min_diff, max_ele - min_ele) if __name__ == '__main__': tc = int(input()) while tc > 0: k = int(input()) n = int(input()) arr = list(map(int, input().strip().split())) ob = Solution() ans = ob.getMinDiff(arr, n, k) print(ans) tc -= 1
But i’m unable to pass the testcases:
Input: 4 10 6 1 9 1 1 7 9 5 2 10 Its Correct output is: 5 And my Code's output is: 6
I’m unable to figure out fault in my logic or code. Could some suggest corrections or better approach?
I’m unable to figure out fault in my logic or code.
As per your current logic, you decide to add or subtract k just based on the current element. But it might not yield the min diff overall. For example, for 5 you decided to add k and it resulted in the range
(5,11) for the whole set. Rather if you have subtracted it would have yielded
Could some suggest corrections or better approach?
if k > (max - min)then directly return
max - min. Since adding k to min and subtracting k from max will yield a larger difference. (To be precise,
2 * k + (max - min))
kto min element and subtract
kfrom max element. There should exist an index in the array, where we switch from adding k to subtracting k. The below diagram shows the switch index:
(Note: In the diagram,
Bcan be less than
D and also
A can be greater than
A < Cthen the range will start with
Aor else with
B > Dthen the range will end with
Bor else with
rangeacross all index gives the result
def getMinDiff(self, arr, n, k): # code here arr.sort() min_diff = arr[-1] - arr if min_diff <= k: return min_diff for i in range(0, n-1): if arr[i + 1] < k : continue start = min(arr + k, arr[i + 1] - k) end = max(arr[-1] - k, arr[i] + k) min_diff = min(min_diff, end - start) return min_diff
arr + kand
next element - ki.e,.
arr[ i + 1 ] - k
current element + k, i.e.,
arr[i] + kand
arr[-1] - k