Queries to find minimum swaps required to sort given array with updates | Function to return the position of the given value using binary search ; Return 0 if every value is greater than the given value ; Return N - 1 if every value is smaller than the given value ; Perform Binary Search ; Iterate till start < end ; Find the mid ; Update start and end ; Return the position of the given value ; Function to return the number of make the array sorted ; Index x to update ; Increment value by y ; Set newElement equals to x + y ; Compute the new index ; Print the minimum number of swaps ; Driver Code ; Given array arr [ ] ; Given Queries ; Function Call
def computePos ( arr , n , value ) : NEW_LINE INDENT if ( value < arr [ 0 ] ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( value > arr [ n - 1 ] ) : NEW_LINE INDENT return n - 1 NEW_LINE DEDENT start = 0 NEW_LINE end = n - 1 NEW_LINE while ( start < end ) : NEW_LINE INDENT mid = ( start + end + 1 ) // 2 NEW_LINE if ( arr [ mid ] >= value ) : NEW_LINE INDENT end = mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT start = mid NEW_LINE DEDENT DEDENT return start NEW_LINE DEDENT def countShift ( arr , n , queries ) : NEW_LINE INDENT for q in queries : NEW_LINE INDENT index = q [ 0 ] NEW_LINE update = q [ 1 ] NEW_LINE newElement = arr [ index ] + update NEW_LINE newIndex = computePos ( arr , n , newElement ) NEW_LINE print ( abs ( newIndex - index ) , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 2 , 3 , 4 , 5 , 6 ] NEW_LINE N = len ( arr ) NEW_LINE queries = [ [ 0 , - 1 ] , [ 4 , - 11 ] ] NEW_LINE countShift ( arr , N , queries ) NEW_LINE DEDENT