0
$\begingroup$

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?

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.