Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Given an array unsorted P of integers and a number m. I am trying to write a code that returns indices i, and j to satisfy 8P[i] + 7P[j] = M with time O(n log n).
I iterated over P[0] to P[n-1] and searched for P[j] = (M - 8P[i])/7 using binary search. Here, I can get the values of P[i] and P[j], but the original index of j is changed while sorting before binary search. What could be the better way to get the index?
Create a $2$-d array $D[n][2]$, where $D[i][0]$ stores $P[i]$, and $D[i][1]$ stores the index $i$.
Sort the array by comparing just the first value. When, swapping the two items of the array, swap their second values also. In this way, you can access the original index value after sorting.
There are other ways to do it. For example, create an array of structure or a pair of two values, etc, and sort the items based on the first value.
