Queries to find minimum swaps required to sort given array with updates | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int computePos ( int arr [ ] , int n , int value ) { if ( value < arr [ 0 ] ) return 0 ; if ( value > arr [ n - 1 ] ) return n - 1 ; int start = 0 ; int end = n - 1 ; while ( start < end ) { int mid = ( start + end + 1 ) / 2 ; if ( arr [ mid ] >= value ) end = mid - 1 ; else start = mid ; } return start ; } void countShift ( int arr [ ] , int n , vector < vector < int > > & queries ) { for ( auto q : queries ) { int index = q [ 0 ] ; int update = q [ 1 ] ; int newElement = arr [ index ] + update ; int newIndex = computePos ( arr , n , newElement ) ; cout << abs ( newIndex - index ) << " ▁ " ; } } int main ( ) { int arr [ ] = { 2 , 3 , 4 , 5 , 6 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; vector < vector < int > > queries = { { 0 , -1 } , { 4 , -11 } } ; countShift ( arr , N , queries ) ; return 0 ; }