Rearrange Distant Barcodes in C++
In this article, we will discuss how we can rearrange distant barcodes in C++.
There are barcodes in a row in a warehouse, and barcode [i] is the ith barcode. Rearrange the barcodes to prevent any two adjacent barcodes from being equivalent. Any response is acceptable, and there is a guarantee that one exists.
Examples:
Barcodes = {1, 1, 1, 2, 2, 2} is entered. {2, 1, 2, 1, 2, 1} is the output.
Explanation: There are never two adjacent barcodes that are equal in {2, 1, 2, 1, 2, 1}.
Barcodes = {1, 1, 1, 2, 2, 3, 3} is entered. {1, 3, 1, 3, 1, 2, 1, 2} is the output.
Explanation: No two adjacent barcodes in {1, 3, 1, 3, 1, 2, 1, 2} are equal.
Let's say there is a row of barcodes in a warehouse. Barcodes[i] are the i-th barcode. The barcodes must be rearranged so that no two barcodes next to each other are the same. Thus, the output is [2,1,2,1,2,1] if the input is [1,1,1,2,2,2].
Step-by-Step Process:
We will take the following actions to resolve this:
1. Create a single map called d.
2. Put the frequency of numbers in the barcode array into the d.
3. x:= Empty list
4. Put each key-value pair into x.
5. Let i = 0.
6. res:= Create a list that has the same length as the barcodes and populate [0].
7. Sort x according to how often
while I < result duration
- result[i]:= Element of the final entry of x.
- Decrease the last entry of x's frequency value.
- Remove the last element of x from x if its frequency is zero.
- Increase I by 2.
8. I = 1.
while I < duration of outcome
- Result[i] = Element of the last entry of x.
- Reduce the frequency value of the last entry of x.
- Delete the last element of x if its frequency is 0.
- Increase i by 2
9. Return outcome.
Use the following concept to solve the problem:
First, the plan is to determine the character frequency using the map. Once they are all added to a heap, try to extract two entries from the heap with each iteration of the while loop. We must remove two pieces from the heap because if we remove only one, the removed element may still appear the most frequently and so become adjacent. Therefore, pop out two at a time to prevent this.
Step-by-step algorithm:
- Use an unordered map to determine how frequently each barcode appears in the input vector.
- Use a priority queue (max-heap) to store the barcodes in descending order of frequency.
- Repeat steps 1 through 3 for every barcode in the priority queue.
- Insert the barcode into the vector that has been altered, omitting any additional positions.
- If the barcode's frequency remain higher than zero, reduce it and re-add it to the priority queue.
- If the additional barcode is present in the priority queue, place it in the rearranged vector at the following location.
- Give the reorganized vector back.
Example:
Let us take an example to illustrate the Rearrange Distant Barcode in C++.
#include <bits/stdc++.h> using namespace std; vector<int> rearrangeBarcodes(vector<int>& barcodes) { // Create a hash map to store barcode frequencies. unordered_map<int, int> map; int n = barcodes.size(); for (int i = 0; i < n; i++) { map[barcodes[i]]++; } // and corresponding values priority_queue<pair<int, int> > heap; for (auto it : map) { heap.push({ it.second, it.first }); } // Rearrange barcodes using the priority queue. vector<int> result; while (!heap.empty()) { // frequency. pair<int, int> temp1 = heap.top(); heap.pop(); result.push_back(temp1.second); temp1.first--; // Invert the negation for proper // count if (!heap.empty()) { // Get the second most frequent barcode (if // available) and decrement its frequency. pair<int, int> temp2 = heap.top(); heap.pop(); result.push_back(temp2.second); temp2.first--; // Push back the second barcode only if it has // remaining occurrences. if (temp2.first > 0) { heap.push(temp2); } } // Push back the first barcode only if it has // remaining occurrences. if (temp1.first > 0) { heap.push(temp1); } } return result; } int main() { // Input: barcodes = [1, 1, 1, 2, 2, 2] vector<int> barcodes = { 1, 1, 1, 2, 2, 2 }; vector<int> rearrangedBarcodes = rearrangeBarcodes(barcodes); cout << "Rearranged barcodes: "; for (int barcode : rearrangedBarcodes) { cout << barcode << " "; } cout << endl; return 0; }
Output:
Rearranged barcodes: 2 1 2 1 2 1