Número de clientes que pueden obtener el sabor deseado del helado

Dados dos sabores de helado de chocolate y vainilla denotados por 0 y 1 respectivamente. La gente hace cola para obtener el sabor deseado de helado de la pila de helado. 

• Si el cliente al frente de la fila prefiere el paquete de helado en la parte superior de la pila, lo tomará y abandonará la fila.
• De lo contrario, lo dejarán y se irán al final de la cola.

El proceso continúa hasta que nadie de la cola quiere tomar el paquete de helado superior.

Dadas dos arrays cliente[] y helado[] donde cliente[i] es la preferencia del cliente i -ésimo cliente (i =0 es el primero de la cola) y helado[i] denota el tipo de i -ésimo helado en la pila (i =0 es la parte superior de la pila). La tarea es encontrar el número de clientes que pueden obtener el sabor deseado de helado. 

Ejemplos: 

Entrada: cliente = {1, 1, 0, 0}, helado = {0, 1, 0, 1}
Salida: 4
Explicación: La siguiente es la secuencia en la que los clientes obtuvieron el sabor de helado que deseaban. 
El cliente del frente deja el paquete de helado superior y se mueve al final de la fila. Ahora cliente = {1, 0, 0, 1}.
El cliente del frente deja el paquete de helado superior y se mueve al final de la fila. Ahora cliente = {0, 0, 1, 1}.
El cliente del frente toma helado y deja la fila. Ahora helado = [1, 0, 1] y cliente = {0, 1, 1}.
El cliente del frente deja el paquete de helado superior y se mueve hacia el final. Ahora cliente = {1, 1, 0} .
El cliente de enfrente toma un paquete de helado y sale de la fila. Ahora helado = {0, 1} y cliente = {1, 0}.
El cliente del frente sale de la fila y pasa al final. Ahora cliente = {0, 1}.
El cliente del frente recibe un paquete de helado y se va de la fila. Ahora cliente = {1} y helado {1}.
El cliente del frente recibe un paquete de helado y ahora la línea está vacía.
Por lo tanto, los cuatro clientes pueden obtener el paquete de helado deseado.

Entrada: cliente = {1, 1, 1, 0, 0, 1}, helado = {1, 0, 0, 0, 1, 1}
Salida: 3

Enfoque 1: este problema se puede resolver utilizando Stack and Queue . Siga los pasos a continuación para resolver el problema dado.   

• Cree una pila y empuje la array icecream[] en la pila .
• Cree una cola y empuje la array del cliente [] en la cola
• Inicialice una variable, por ejemplo, topRejected=0 para realizar un seguimiento del elemento rechazado.
• Si el frente de la cola es igual a la parte superior de la pila, saque los elementos de la pila y elimine el elemento de la cola y actualice topRejected=0 .
• De lo contrario, incremente el recuento de topRejected y elimine el elemento del frente de la cola y agréguelo en último lugar.
• Si el tamaño de la cola es igual a topRejected , interrumpa el ciclo.
• Imprima icecream.length – queue.size como la respuesta requerida (porque el elemento restante en la cola no podrá obtener el paquete de helado deseado).

/*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 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);
    }
}

/*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

4

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(N)

Enfoque 2: el enfoque anterior se puede optimizar aún más y se puede evitar el espacio O(N) adicional. Siga los pasos a continuación para resolver el problema dado.   

• Almacenar el orden de la cola no sirve de nada.
• Declare una array, digamos count[] , que hará un seguimiento de las preferencias del cliente.
• Incremente el conteo[0] si el cliente[i] es 0 , de lo contrario incremente el conteo[1] .
• Ahora, inicialice k , que almacenará la cantidad de clientes que obtendrán el paquete de helado deseado.
• Repita la array de helados y verifique si alguien en el cliente izquierdo tomará comida.
• Por fin imprima k como la respuesta final.

// 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 cream
int 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 program for above approach
import 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 program for above approach
 
# Function to find the number
# of customers who will
# get their desired flavor of ice cream
def 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# program for above approach
using 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

<script>
// Javascript program for above approach
 
// Function to find the number
// of customers who will
// get their desired flavor of ice cream
function 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 answer
document.write(ans);
 
// This code is contributed by gfgking
 
</script>

4

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(1)