Dado un objetivo entero y una array arr[] que consiste en N enteros positivos donde arr[i] denota el tiempo requerido para obtener 1 punto para el i -ésimo elemento de la array, la tarea es encontrar el tiempo mínimo requerido para obtener la puntuación objetivo de la array dada.
Ejemplos:
Entrada: arr[] = {1, 3, 3, 4}, destino = 10
Salida: 6
Explicación:
En el instante de tiempo, t = 1: Puntuación de la array: {1, 0, 0, 0}
En el instante de tiempo, t = 2: Puntuación de la array: {2, 0, 0, 0}
En el instante de tiempo, t = 3: Puntuación de la array: {3, 1, 1, 0}
En el instante de tiempo, t = 4: Puntuación de la array: {4, 1, 1, 1}
En el instante de tiempo, t = 5: Puntuación de la array: {5, 1, 1, 1}
En el instante de tiempo, t = 6: Puntuación de la array: {6, 2, 2, 1}
Puntuación total de la array después de t = 5 = 6 + 2 + 2 + 1 = 11 ( > 10). Por lo tanto, losEntrada: arr[] = {2, 4, 3}, objetivo = 20
Salida: 20
Enfoque: la idea es usar Hashing para almacenar la frecuencia de los elementos de la array e iterar sobre Hashmap y seguir actualizando la puntuación hasta que alcance el objetivo . Una observación importante es que cualquier elemento, arr[i] suma t / arr[i] a la puntuación en cualquier instante de tiempo t . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos tiempo , para almacenar el tiempo mínimo requerido y sume 0 para almacenar la puntuación en cualquier instante de tiempo t .
- Almacene la frecuencia de los elementos de la array en un Hashmap M .
- Iterar hasta que la suma sea menor que el objetivo y realizar los siguientes pasos:
- Establezca la suma en 0 e incremente el valor del tiempo en 1 .
- Ahora, recorra el hashmap M e incremente el valor de sum por frecuencia * (tiempo/valor) en cada iteración.
- Después de completar los pasos anteriores, imprima el valor del tiempo como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate minimum time
// required to achieve given score target
void findMinimumTime(int* p, int n,
int target)
{
// Store the frequency of elements
unordered_map<int, int> um;
// Traverse the array p[]
for (int i = 0; i < n; i++) {
// Update the frequency
um[p[i]]++;
}
// Stores the minimum time required
int time = 0;
// Store the current score
// at any time instant t
int sum = 0;
// Iterate until sum is at
// least equal to target
while (sum < target) {
sum = 0;
// Increment time with
// every iteration
time++;
// Traverse the map
for (auto& it : um) {
// Increment the points
sum += it.second
* (time / it.first);
}
}
// Print the time required
cout << time;
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 3, 4 };
int N = sizeof(arr) / sizeof(arr[0]);
int target = 10;
// Function Call
findMinimumTime(arr, N, target);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
import java.io.*;
class GFG{
// Function to calculate minimum time
// required to achieve given score target
static void findMinimumTime(int [] p, int n,
int target)
{
// Store the frequency of elements
HashMap<Integer,
Integer> um = new HashMap<>();
// Traverse the array p[]
for(int i = 0; i < n; i++)
{
// Update the frequency
if (!um.containsKey(p[i]))
um.put(p[i], 1);
else
um.put(p[i],
um.get(p[i]) + 1);
}
// Stores the minimum time required
int time = 0;
// Store the current score
// at any time instant t
int sum = 0;
while (sum < target)
{
sum = 0;
// Increment time with
// every iteration
time++;
// Traverse the map
for(Map.Entry<Integer,
Integer> it : um.entrySet())
{
// Increment the points
sum += it.getValue() * (time / it.getKey());
}
}
// Print the time required
System.out.println(time);
}
// Driver Code
public static void main(String args[])
{
int[] arr = { 1, 3, 3, 4 };
int N = arr.length;
int target = 10;
// Function Call
findMinimumTime(arr, N, target);
}
}
// This code is contributed by susmitakundugoaldanga
Python3
# Python3 program for the above approach
# Function to calculate minimum time
# required to achieve given score target
def findMinimumTime(p, n, target):
# Store the frequency of elements
um = {}
# Traverse the array p[]
for i in range(n):
# Update the frequency
um[p[i]] = um.get(p[i], 0) + 1
# Stores the minimum time required
time = 0
# Store the current score
# at any time instant t
sum = 0
# Iterate until sum is at
# least equal to target
while (sum < target):
sum = 0
# Increment time with
# every iteration
time += 1
# Traverse the map
for it in um:
# Increment the points
sum += um[it] * (time // it)
# Print time required
print(time)
# Driver Code
if __name__ == '__main__':
arr = [1, 3, 3, 4]
N = len(arr)
target = 10
# Function Call
findMinimumTime(arr, N, target)
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System.Collections.Generic;
using System;
using System.Linq;
class GFG{
// Function to calculate minimum time
// required to achieve given score target
static void findMinimumTime(int [] p, int n,
int target)
{
// Store the frequency of elements
Dictionary<int,
int> um = new Dictionary<int,
int>();
// Traverse the array p[]
for(int i = 0; i < n; i++)
{
// Update the frequency
if (um.ContainsKey(p[i]) == true)
um[p[i]] += 1;
else
um[p[i]] = 1;
}
// Stores the minimum time required
int time = 0;
// Store the current score
// at any time instant t
int sum = 0;
// Iterate until sum is at
// least equal to target
var val = um.Keys.ToList();
while (sum < target)
{
sum = 0;
// Increment time with
// every iteration
time++;
// Traverse the map
foreach(var key in val)
{
// Increment the points
sum += um[key] * (time / key);
}
}
// Print the time required
Console.WriteLine(time);
}
// Driver Code
public static void Main()
{
int []arr = { 1, 3, 3, 4 };
int N = arr.Length;
int target = 10;
// Function Call
findMinimumTime(arr, N, target);
}
}
// This code is contributed by Stream_Cipher
Javascript
<script>
// Js program for the above approach
// Function to calculate minimum time
// required to achieve given score target
function findMinimumTime( p, n,
target)
{
// Store the frequency of elements
let um = new Map();
// Traverse the array p[]
for (let i = 0; i < n; i++) {
// Update the frequency
if(um[p[i]])
um[p[i]]++;
else
um[p[i]] = 1
}
// Stores the minimum time required
let time = 0;
// Store the current score
// at any time instant t
let sum = 0;
// Iterate until sum is at
// least equal to target
while (sum < target) {
sum = 0;
// Increment time with
// every iteration
time++;
// Traverse the map
for (let it in um) {
// Increment the points
sum += um[it]
* Math.floor(time / it);
}
}
// Print the time required
document.write(time);
}
// Driver Code
let arr = [1, 3, 3, 4];
let N = arr.length;
let target = 10;
// Function Call
findMinimumTime(arr, N, target);
// This code is contributed by rohitsingh07052.
</script>
6
Complejidad de tiempo: O(objetivo*N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ananyadixit8 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA