Given two flavors of ice-cream chocolate and vanilla denoted by 0 and 1 respectively. People are standing in queue to get their desired flavor of ice cream from the stack of ice cream.
- If the customer at the front of the queue prefers the ice cream pack on the top of the stack, they will take it and leave the queue.
- Otherwise, they will leave it and go to the queue’s end.
The process continues until no one from the queue wants to take the top ice cream pack.
Given two arrays customer[] and icecream[] where customer[i] is the preference of the customer ith customer(i =0 is the front of the queue) and icecream[i] denotes the type of ith icecream in the stack(i =0 is the top of the stack). The task is to find the number of customers able to get their desired flavor of ice cream.
Examples:
Input: customer = {1, 1, 0, 0}, icecream = {0, 1, 0, 1}
Output: 4
Explanation: Following is the sequence in which customers got their desired flavor of ice cream.
Front customer leaves top icecream pack and move to end of line . Now customer = {1, 0, 0, 1}.
Front customer leaves top icecream pack and moves to end of line . Now customer = {0, 0, 1, 1}.
Front customer get icecream and leave line. Now icecream = [1, 0, 1] and customer = {0, 1, 1}.
Front customer leaves top icecream pack and move to end. Now customer = {1, 1, 0} .
Front customer get icecream pack and leaves the line. Now icecream = {0, 1} and customer = {1, 0}.
Front customer leaves line and move to end. Now customer = {0, 1}.
Front customer get icecream pack and leaves line. Now customer = {1} and icecream {1}.
Front customer get icecream pack and now line is empty.
Therefore, all four customer able to get desired icecream pack.Input: customer = {1, 1, 1, 0, 0, 1}, icecream = {1, 0, 0, 0, 1, 1}
Output: 3
Approach 1: This problem can be solved by using Stack and Queue. Follow the steps below to solve the given problem.
- Create a stack and push icecream[] array in the stack.
- Create a queue and push customer[] array in queue
- Initialize a variable say, topRejected=0 to keep track of rejected element.
- If the front of the queue is equal to the stack top pop elements from the stack and remove the element from the queue and update topRejected=0.
- Else increment the count of topRejected and remove the element from the front of queue and add in last.
- If the queue size is equal to topRejected then break loop.
- Print icecream.length–queue.size as the required answer(because the remaining element in the queue will not be able to get desired ice cream pack).
C++
/*C++ implementation of above approach*/#include <bits/stdc++.h>using namespace std;void NumberOfCustomer(int customer[],int icecream[],int customer_size,int icecream_size){ stack<int> stack; queue<int> queue; for (int i = icecream_size - 1; i >= 0; i--) { stack.push(icecream[i]); } for (int i = 0; i < customer_size; i++) { queue.push(customer[i]); } int topRejected = 0; while (true) { if (topRejected == queue.size()) break; if (queue.front() == stack.top()) { queue.pop(); stack.pop(); topRejected = 0; } else { topRejected++; queue.push(queue.front()); queue.pop(); } } cout << icecream_size - queue.size();}int main(){ int customer[] = { 1, 1, 0, 0 }; int icecream[] = { 0, 1, 0, 1 }; int customer_size = sizeof(customer)/sizeof(customer[0]); int icecream_size = sizeof(icecream)/sizeof(icecream[0]); NumberOfCustomer(customer, icecream, customer_size, icecream_size); return 0;}//This code is contributed by adityapatil12 |
Java
/*Java implementation of above approach*/import java.io.*;import java.util.*;class GFG { public static void NumberOfCustomer( int[] customer, int[] icecream) { Stack<Integer> stack = new Stack<>(); Queue<Integer> queue = new LinkedList<>(); for (int i = icecream.length - 1; i >= 0; i--) { stack.push(icecream[i]); } for (int i = 0; i < customer.length; i++) { queue.add(customer[i]); } int topRejected = 0; while (true) { if (topRejected == queue.size()) break; if (queue.peek() == stack.peek()) { queue.remove(); stack.pop(); topRejected = 0; } else { topRejected++; queue.add(queue.remove()); } } System.out.println( icecream.length - queue.size()); } public static void main(String[] args) { int customer[] = { 1, 1, 0, 0 }; int icecream[] = { 0, 1, 0, 1 }; NumberOfCustomer(customer, icecream); }} |
Python3
# Python implementation of the above approachfrom collections import dequedef NumberOfCustomer(customer, icecream): # stack stack = [] # Inbuild queue queue = deque() for i in range(len(icecream)-1, -1, -1): stack.append(icecream[i]) for i in range(len(customer)): queue.append(customer[i]) topRejected = 0 while True: if topRejected == len(queue): break if queue[0] == stack[-1]: queue.popleft() stack.pop() topRejected = 0 else: topRejected += 1 queue.append(queue.popleft()) print(len(icecream) - len(queue))customer = [1, 1, 0, 0]icecream = [0, 1, 0, 1]NumberOfCustomer(customer, icecream)# This code is contributed by lokesh |
C#
/*C# implementation of above approach*/using System;using System.Collections.Generic;public class GFG { public static void NumberOfCustomer( int[] customer, int[] icecream) { Stack<int> stack = new Stack<int>(); Queue<int> queue = new Queue<int>(); for (int i = icecream.Length - 1; i >= 0; i--) { stack.Push(icecream[i]); } for (int i = 0; i < customer.Length; i++) { queue.Enqueue(customer[i]); } int topRejected = 0; while (true) { if (topRejected == queue.Count) break; if (queue.Peek() == stack.Peek()) { queue.Dequeue(); stack.Pop(); topRejected = 0; } else { topRejected++; queue.Enqueue(queue.Dequeue()); } } Console.WriteLine( icecream.Length - queue.Count); } public static void Main(String[] args) { int[]customer = { 1, 1, 0, 0 }; int[] icecream = { 0, 1, 0, 1 }; NumberOfCustomer(customer, icecream); }}// This code is contributed by 29AjayKumar |
Javascript
/* JavaScript implementation of above approach */const NumberOfCustomer = (customer, icecream) => {const stack = [];const queue = [];for (let i = icecream.length - 1; i >= 0; i--) { stack.push(icecream[i]);}for (let i = 0; i < customer.length; i++) { queue.push(customer[i]);}let topRejected = 0;while (true) { if (topRejected === queue.length) break; if (queue[0] === stack[stack.length - 1]) { queue.shift(); stack.pop(); topRejected = 0; } else { topRejected++; queue.push(queue.shift()); } } console.log(icecream.length - queue.length);};const customer = [1, 1, 0, 0];const icecream = [0, 1, 0, 1];NumberOfCustomer(customer, icecream);// This code is contributed by lokeshmvs21. |
Output
4
Time Complexity: O(N)
Auxiliary Space: O(N)
Approach 2: Above approach can be further optimized and extra O(N) space can be avoided. Follow the steps below to solve the given problem.
- Storing the order of the queue is of no use.
- Declare an array say count[] that will keep track of customer preferences.
- Increment count[0] if customer[i] is 0, else increment count[1].
- Now, Initialize k which will store the number of customers who will get desired ice cream pack.
- Iterate through icecream array and check if anyone in left customer will take food.
- At last print k as the final answer.
C++
// c++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to find the number// of customers who will// get their desired flavor of ice creamint NumberOfCustomer(int customer[], int icecream[], int n){ // Count array stores the count // of preference of the customer int count[] = { 0, 0 }; int k = 0; for (int a = 0; a < n; a++) { count[customer[a]]++; } for (k = 0; k < n && count[icecream[k]] > 0; ++k) { count[icecream[k]]--; } // Return k as the final answer return k;}int main(){ int customer[] = { 1, 1, 0, 0 }; int icecream[] = { 0, 1, 0, 1 }; int n = sizeof(customer) / sizeof(customer[0]); int ans = NumberOfCustomer(customer, icecream, n); // Print the final answer cout << (ans); return 0;}// This code is contributed by ukasp. |
Java
// Java program for above approachimport java.io.*;import java.util.*;class GFG { // Function to find the number // of customers who will // get their desired flavor of ice cream public static int NumberOfCustomer( int[] customer, int[] icecream) { // Count array stores the count // of preference of the customer int count[] = { 0, 0 }; int n = customer.length; int k; for (int a : customer) { count[a]++; } for (k = 0; k < n && count[icecream[k]] > 0; ++k) { count[icecream[k]]--; } // Return k as the final answer return k; } public static void main(String[] args) { int customer[] = { 1, 1, 0, 0 }; int icecream[] = { 0, 1, 0, 1 }; int ans = NumberOfCustomer( customer, icecream); // Print the final answer System.out.print(ans); }} |
Python3
# Python3 program for above approach# Function to find the number# of customers who will# get their desired flavor of ice creamdef NumberOfCustomer(customer, icecream) : # Count array stores the count # of preference of the customer count = [ 0, 0 ]; n = len(customer); for a in customer : count[a] += 1; k = 0 while k < n and count[icecream[k]] > 0 : count[icecream[k]] -= 1; k += 1; # Return k as the final answer return k;if __name__ == "__main__" : customer = [1, 1, 0, 0]; icecream = [0, 1, 0, 1]; ans = NumberOfCustomer(customer, icecream); print(ans); # This code is contributed by AnkThon |
C#
// C# program for above approachusing System;class GFG { // Function to find the number // of customers who will // get their desired flavor of ice cream public static int NumberOfCustomer( int[] customer, int[] icecream) { // Count array stores the count // of preference of the customer int[] count = { 0, 0 }; int n = customer.Length; int k; foreach(int a in customer) { count[a]++; } for (k = 0; k < n && count[icecream[k]] > 0; ++k) { count[icecream[k]]--; } // Return k as the final answer return k; } public static void Main() { int[] customer = { 1, 1, 0, 0 }; int[] icecream = { 0, 1, 0, 1 }; int ans = NumberOfCustomer( customer, icecream); // Print the final answer Console.Write(ans); }}// This code is contributed by gfgking |
Javascript
<script>// Javascript program for above approach// Function to find the number// of customers who will// get their desired flavor of ice creamfunction NumberOfCustomer(customer, icecream){ // Count array stores the count // of preference of the customer let count = [0, 0]; let n = customer.length; let k; for (a of customer) { count[a]++; } for (k = 0; k < n && count[icecream[k]] > 0; ++k) { count[icecream[k]]--; } // Return k as the final answer return k;}let customer = [1, 1, 0, 0]let icecream = [0, 1, 0, 1]let ans = NumberOfCustomer(customer, icecream);// Print the final answerdocument.write(ans);// This code is contributed by gfgking</script> |
Output
4
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
