//***************************************** //If there are four person, their order in queue is 1,2,3 and 4 //Someone can give a bribe to go ahead of the person in queue and queue gets updated //for example, 2 can give a bribe to 1 and queue becomes 2,1,3,4... with this, 2 has already given a bribe to others once... // constraint is that any one person can give max two bribe to other persons where as any one person can get as many as possible bribe from others (for example, person A can give bribe to two others , but he can take any number of bribes) // final queue is your input and you have to answer howmany bribes were given to achieve the input queue.. If conatraint above is not satisfied, answer is -1 bribe... // Input 1 : 1,3,4,2 and output is 2... // explanation : initially it was 1,2,3,4 and 3 gave first bribe to 2... Queue is 1,3,2,4.. Now, 4 gives his first (total second) to 2 and queue is 1,3,4,2... This queue is input and asnwer is 2 bribes // Input 2 : 4,3,1,2 and output is -1... // explanation : initially queue is 1,2,3,4 and for final queue, 4 should go from fourth to first position.. means he individually has to give 3 bribes and this violates constraint of max 2 bribes.. So, ouput is -1 //Input 3 : 1,2,5,3,7,8,6,4 and output is 7... // explanation : // bribe 1 : 12354678 // 5 gave 1 no bribe // bribe 2 : 12534678 // 5 gave 2 no bribe // bribe 3 : 12534768 // 7 gave 1 no bribe // bribe 4 : 12537468 // 7 gave 2 no bribe // bribe 5 : 12537486 // 8 gave 1 no bribe // bribe 6 : 12537846 // 8 gave 2 no bribe // bribe 7 : 12537864 // 6 gave 1 no bribe //****************************************** #include #include #include using namespace std; int findPos (int arr[], int n, int val) { for (int i = 0; i < n; ++i) { if (arr[i] == val) { return i; } } return -1; } //Main function to calculate count of bribe void CalculateBribe(vectorvecFinalQueue) { //total in queue int intTotal = vecFinalQueue.size(); //initial arrangement of queue...Serial number to all from 1 to n for n person int ArrInitialQueue[intTotal]; for (int intCur = 0; intCur < intTotal; ++intCur) { ArrInitialQueue[intCur] = intCur + 1; } int ArrOutput[intTotal] = { 0 };//initialize to zero for indiviual person's bribe count //loop through all on final queue. for (int intCur = 0; intCur < intTotal; ++intCur) { int intKeyVal = vecFinalQueue[intCur]; //If initial queue value doesnot match with final value, do change values in intitial queue while (intKeyVal !=ArrInitialQueue[intCur]) { int intPos = findPos (ArrInitialQueue, intTotal, intKeyVal); //swap number in initial queue int intTemp = ArrInitialQueue[intPos - 1]; ArrInitialQueue[intPos - 1] = intKeyVal; ArrInitialQueue[intPos] = intTemp; //Increment value of position change ArrOutput[intKeyVal - 1] += 1; } } int intTotalBribe = 0; for (int intCur = 0; intCur < intTotal; ++intCur) { //Indiviual person bribe is added into total bribe count intTotalBribe += ArrOutput[intCur]; if (ArrOutput[intCur] > 2) // if bribe of Indiviual is more than 2, return with -1 as it's violation of constraint given { cout << -1 << endl; return; } } //Total bribe count cout << intTotalBribe << endl; } int main () { //input series..Comment different cases //vector vecFinalQueue = { 1, 3, 4, 2 }; //vector vecFinalQueue = {4,3,1,2}; vector vecFinalQueue = { 1, 2, 5, 3, 7, 8, 6, 4 }; //Main function to calculate bribe count to come up with final series as inputted by user CalculateBribe(vecFinalQueue); return 0; }

BribeCalculator