This is the code https://ide.codingblocks.com/s/343317
Now I will break down the code.
Okay so the thing is you generate all the possible values element at a particular index can give and store them in a list(vector) corresponding to each index.
vector<vector<int> > convertToLists(vector<int> &a, int k) {
vector<vector<int> >lists(a.size());
vector<int>curElem;
for (int i = 0; i < a.size(); i++) {
int cur = a[i];
curElem.clear();
curElem.push_back(cur);
if (cur % k == 0) {
while (cur % k == 0) {
cur /= k;
curElem.push_back(cur);
}
reverse(curElem.begin(), curElem.end());
} else {
curElem.push_back(a[i] * k);
}
lists[i] = curElem;
}
return lists;
}
Remember we are storing the lists in ascending order. Now we push the smallest element of each list into the priority queue.
priority_queue<Node, vector<Node>, comp> pq;
int high = INT_MIN;
for (int i = 0; i < lists.size(); i++){
if (lists[i].size()) {
// elem, list_num, idx
pq.push({lists[i][0], i, 0});
high = max(high, lists[i][0]);
}
}
Store the maximum element up until now.
Now the logic is that at any time we store only one element corresponding to each list in the priority queue, and check the difference at that particular time between max element and min element.
Also priority queue here is designed to store elements in ascending order.
int low = pq.top().value;
int list_num = pq.top().list_num;
int idx = pq.top().index;
pq.pop();
if (high - low < ans.second - ans.first) {
ans = {low, high};
}
After this when some list exhausts, we terminate our finding and return the best answer till now.(This should be obvious as to why we are doing this).
if (idx == lists[list_num].size() - 1) {
return ans;
}
If list is not finished , we push the next element in the queue and also compare it with maximum and update the maximum.
pq.push({lists[list_num][idx + 1], list_num, idx + 1});
high = max(high, lists[list_num][idx + 1]);
