Given lengths of n rods in an array a[]. If any person picks any rod, half of the longest rod (or (max + 1) / 2 ) is assigned and remaining part (max – 1) / 2 is put back. It may be assumed that sufficient number of rods are always available, answer M queries given in an array q[] to find the largest length of rod available for qith person, provided qi is a valid person number starting from 1.
Examples :
Input : a[] = {6, 5, 9, 10, 12}
q[] = {1, 3}
Output : 12 9
The first person gets maximum length as 12.
We remove 12 from array and put back (12 -1) / 2 = 5.
Second person gets maximum length as 10.
We put back (10 - 1)/2 which is 4.
Third person gets maximum length as 9.
Input : a[] = {6, 5, 9, 10, 12}
q[] = {3, 1, 2, 7, 4, 8, 9, 5, 10, 6}
Output : 9 12 10 5 6 4 3 6 3 5
Approach :
Use a stack and a queue. First sort all the lengths and push them onto a stack. Now, take the top element of stack, and divide by 2 and push the remaining length to queue. Now, from next customer onwards :
- If stack is empty, pop front queue and push back to queue. It’s half (front / 2), if non zero.
- If queue is empty, pop from stack and push to queue it’s half (top / 2), if non zero.
- If both are non empty, compare top and front, which ever is larger should be popped, divided by 2 and then pushed back.
- If both are empty, store is empty! Stop here!
At each step above store the length available to ith customer in separate array, say “ans”. Now, start answering the queries by giving ans[Qi] as output.
Below is the implementation of above approach :
C++
// CPP code to find the length of largest// rod available for Q-th customer#include <bits/stdc++.h>using namespace std;// function to find largest length of// rod available for Q-th customervector<int> maxRodLength(int ar[], int n, int m){ queue<int> q; // sort the rods according to lengths sort(ar, ar + n); // Push sorted elements to a stack stack<int> s; for (int i = 0; i < n; i++) s.push(ar[i]); vector<int> ans; while (!s.empty() || !q.empty()) { int val; // If queue is empty -> pop from stack // and push to queue it’s half(top/2), // if non zero. if (q.empty()) { val = s.top(); ans.push_back(val); s.pop(); val /= 2; if (val) q.push(val); } // If stack is empty -> pop front from // queue and push back to queue it’s // half(front/2), if non zero. else if (s.empty()) { val = q.front(); ans.push_back(val); q.pop(); val /= 2; if (val != 0) q.push(val); } // If both are non empty -> // compare top and front, whichsoever is // larger should be popped, divided by 2 // and then pushed back. else { val = s.top(); int fr = q.front(); if (fr > val) { ans.push_back(fr); q.pop(); fr /= 2; if (fr) q.push(fr); } else { ans.push_back(val); s.pop(); val /= 2; if (val) q.push(val); } } } return ans;}// Driver codeint main(){ // n : number of rods // m : number of queries int n = 5, m = 10; int ar[n] = { 6, 5, 9, 10, 12 }; vector<int> ans = maxRodLength(ar, n, m); int query[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int size = sizeof(query) / sizeof(query[0]); for (int i = 0; i < size; i++) cout << ans[query[i] - 1] << " "; return 0;} |
Java
// JAVA code to find the length of largest// rod available for Q-th customerimport java.util.*;class GFG{// function to find largest length of// rod available for Q-th customerstatic Vector<Integer> maxRodLength(int ar[], int n, int m){ Queue<Integer> q = new LinkedList<>(); // sort the rods according to lengths Arrays.sort(ar); // Push sorted elements to a stack Stack<Integer> s = new Stack<Integer>(); for (int i = 0; i < n; i++) s.add(ar[i]); Vector<Integer> ans = new Vector<Integer>(); while (!s.isEmpty() || !q.isEmpty()) { int val; // If queue is empty.pop from stack // and push to queue its half(top/2), // if non zero. if (q.isEmpty()) { val = s.peek(); ans.add(val); s.pop(); val /= 2; if (val > 0) q.add(val); } // If stack is empty.pop front from // queue and push back to queue its // half(front/2), if non zero. else if (s.isEmpty()) { val = q.peek(); ans.add(val); q.remove(); val /= 2; if (val != 0) q.add(val); } // If both are non empty . // compare top and front, whichsoever is // larger should be popped, divided by 2 // and then pushed back. else { val = s.peek(); int fr = q.peek(); if (fr > val) { ans.add(fr); q.remove(); fr /= 2; if (fr > 0) q.add(fr); } else { ans.add(val); s.pop(); val /= 2; if (val > 0) q.add(val); } } } return ans;}// Driver codepublic static void main(String[] args){ // n : number of rods // m : number of queries int n = 5, m = 10; int []ar = { 6, 5, 9, 10, 12 }; Vector<Integer> ans = maxRodLength(ar, n, m); int query[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int size = query.length; for (int i = 0; i < size; i++) System.out.print(ans.get(query[i] - 1) + " ");}}// This code is contributed by Rajput-Ji |
Python3
# Python3 code to find the length of largest# rod available for Q-th customer# function to find largest length of# rod available for Q-th customerdef maxRodLength(ar, n, m): q = [] # sort the rods according to lengths ar.sort() # Push sorted elements to a stack s = [] for i in range(n): s.append(ar[i]) ans = [] while len(s) != 0 or len(q) != 0 : # If queue is empty.pop from stack # and push to queue its half(top/2), # if non zero. if len(q) == 0: val = s[-1] ans.append(val) s.pop() val = int(val / 2) if (val > 0): q.append(val) # If stack is empty.pop front from # queue and push back to queue its # half(front/2), if non zero. elif len(s) == 0: val = q[0] ans.append(val) q.pop(0) val = int(val / 2) if (val != 0): q.append(val) # If both are non empty . # compare top and front, whichsoever is # larger should be popped, divided by 2 # and then pushed back. else: val = s[-1] fr = q[0] if (fr > val): ans.append(fr) q.pop(0) fr = int(fr / 2) if (fr > 0): q.append(fr) else: ans.append(val) s.pop() val = int(val / 2) if (val > 0): q.append(val) return ans# n : number of rods# m : number of queriesn, m = 5, 10 ar = [ 6, 5, 9, 10, 12 ]ans = maxRodLength(ar, n, m)query = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]size = len(query)for i in range(size): print(ans[query[i] - 1], end = " ") # This code is contributed by decode2207. |
C#
// C# code to find the length of largest// rod available for Q-th customerusing System;using System.Collections.Generic;class GFG { // function to find largest length of // rod available for Q-th customer static List<int> maxRodLength(int[] ar, int n, int m) { Queue<int> q = new Queue<int>(); // sort the rods according to lengths Array.Sort(ar); // Push sorted elements to a stack Stack<int> s = new Stack<int>(); for (int i = 0; i < n; i++) s.Push(ar[i]); List<int> ans = new List<int>(); while (s.Count > 0 || q.Count > 0) { int val; // If queue is empty.pop from stack // and push to queue its half(top/2), // if non zero. if (q.Count == 0) { val = s.Peek(); ans.Add(val); s.Pop(); val /= 2; if (val > 0) q.Enqueue(val); } // If stack is empty.pop front from // queue and push back to queue its // half(front/2), if non zero. else if (s.Count == 0) { val = q.Peek(); ans.Add(val); q.Dequeue(); val /= 2; if (val != 0) q.Enqueue(val); } // If both are non empty . // compare top and front, whichsoever is // larger should be popped, divided by 2 // and then pushed back. else { val = s.Peek(); int fr = q.Peek(); if (fr > val) { ans.Add(fr); q.Dequeue(); fr /= 2; if (fr > 0) q.Enqueue(fr); } else { ans.Add(val); s.Pop(); val /= 2; if (val > 0) q.Enqueue(val); } } } return ans; } // Driver code static void Main() { // n : number of rods // m : number of queries int n = 5, m = 10; int[] ar = { 6, 5, 9, 10, 12 }; List<int> ans = maxRodLength(ar, n, m); int[] query = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int size = query.Length; for (int i = 0; i < size; i++) { Console.Write(ans[query[i] - 1] + " "); } }}// This code is contributed by divyesh072019 |
Javascript
<script> // Javascript code to find the length of largest // rod available for Q-th customer // function to find largest length of // rod available for Q-th customer function maxRodLength(ar, n, m) { let q = []; // sort the rods according to lengths ar.sort(function(a, b){return a - b}); // Push sorted elements to a stack let s = []; for (let i = 0; i < n; i++) s.push(ar[i]); let ans = []; while (s.length > 0 || q.length > 0) { let val; // If queue is empty.pop from stack // and push to queue its half(top/2), // if non zero. if (q.length == 0) { val = s[s.length - 1]; ans.push(val); s.pop(); val = parseInt(val / 2, 10); if (val > 0) q.push(val); } // If stack is empty.pop front from // queue and push back to queue its // half(front/2), if non zero. else if (s.length == 0) { val = q[0]; ans.push(val); q.shift(); val = parseInt(val / 2, 10); if (val != 0) q.push(val); } // If both are non empty . // compare top and front, whichsoever is // larger should be popped, divided by 2 // and then pushed back. else { val = s[s.length - 1]; let fr = q[0]; if (fr > val) { ans.push(fr); q.shift(); fr = parseInt(fr / 2, 10); if (fr > 0) q.push(fr); } else { ans.push(val); s.pop(); val = parseInt(val / 2, 10); if (val > 0) q.push(val); } } } return ans; } // n : number of rods // m : number of queries let n = 5, m = 10; let ar = [ 6, 5, 9, 10, 12 ]; let ans = maxRodLength(ar, n, m); let query = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]; let size = query.length; for (let i = 0; i < size; i++) document.write(ans[query[i] - 1] + " ");// This code is contributed by divyeshrabadiya07.</script> |
Output
12 10 9 6 6 5 5 4 3 3
Time complexity : O(N log(N))
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
