Hay algunos conejos de colores en un bosque. Dada una array arr[] de tamaño N , tal que arr[i] denota el número de conejos que tienen el mismo color que el i -ésimo conejo, la tarea es encontrar el número mínimo de conejos que podría haber en el bosque.
Ejemplos:
Entrada: arr[] = {2, 2, 0}
Salida: 4
Explicación: Considerando que el 1er y el 2do conejo son del mismo color, ej. Azul , debe haber 3 conejos de color azul. El tercer conejo es el único conejo de ese color. Por lo tanto, el número mínimo de conejos que podrían estar presentes en el bosque son = 3 + 1 = 4.Entrada: arr[] = {10, 10, 10}
Salida: 11
Explicación: Considerando que todos los conejos son del mismo color, el número mínimo de conejos presentes en el bosque es 10 + 1 = 11.
Enfoque: El enfoque para resolver este problema es encontrar el número de grupos de conejos que tienen el mismo color y el número de conejos en cada grupo. A continuación se muestran los pasos:
- Inicialice un conteo variable para almacenar el número de conejos en cada grupo.
- Inicialice un mapa y recorra la array que tiene la clave como arr[i] y el valor como ocurrencias de arr[i] en la array dada.
- Ahora, si y conejos respondieron x , entonces:
- Si (y%(x + 1)) es 0 , entonces debe haber (y / (x + 1)) grupos de (x + 1) conejos.
- Si (y % (x + 1)) no es cero, entonces debe haber (y / (x + 1)) + 1 grupos de (x + 1) conejos.
- Agregue el producto del número de grupos y el número de conejos en cada grupo a la variable cuenta .
- Después de los pasos anteriores, el valor de conteo da el número mínimo de conejos en el bosque.
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 find the minimum
// number of rabbits in the forest
int minNumberOfRabbits(int answers[], int N)
{
// Initialize map
map<int, int> Map;
// Traverse array and map arr[i]
// to the number of occurrences
for (int a = 0; a < N; a++) {
Map[answers[a]]++;
}
// Initialize count as 0;
int count = 0;
// Find the number groups and
// no. of rabbits in each group
for (auto a : Map) {
int x = a.first;
int y = a.second;
// Find number of groups and
// multiply them with number
// of rabbits in each group
if (y % (x + 1) == 0)
count = count + (y / (x + 1)) * (x + 1);
else
count = count + ((y / (x + 1)) + 1) * (x + 1);
}
// count gives minimum number
// of rabbits in the forest
return count;
}
// Driver code
int main()
{
int arr[] = { 2, 2, 0 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << minNumberOfRabbits(arr, N) << endl;
return 0;
}
// This code is contributed by divyeshrabadiya07
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find the minimum
// number of rabbits in the forest
public static int minNumberOfRabbits(int[] answers,
int N)
{
// Initialize map
Map<Integer, Integer> map
= new HashMap<Integer, Integer>();
// Traverse array and map arr[i]
// to the number of occurrences
for (int a : answers) {
map.put(a, map.getOrDefault(a, 0) + 1);
}
// Initialize count as 0;
int count = 0;
// Find the number groups and
// no. of rabbits in each group
for (int a : map.keySet()) {
int x = a;
int y = map.get(a);
// Find number of groups and
// multiply them with number
// of rabbits in each group
if (y % (x + 1) == 0) {
count = count + (y / (x + 1)) * (x + 1);
}
else
count
= count + ((y / (x + 1)) + 1) * (x + 1);
}
// count gives minimum number
// of rabbits in the forest
return count;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 2, 0 };
int N = arr.length;
// Function Call
System.out.println(minNumberOfRabbits(arr, N));
}
}
Python3
# Python3 program for the above approach
# Function to find the minimum
# number of rabbits in the forest
def minNumberOfRabbits(answers, N):
# Initialize map
Map = {}
# Traverse array and map arr[i]
# to the number of occurrences
for a in range(N):
if answers[a] in Map:
Map[answers[a]] += 1
else:
Map[answers[a]] = 1
# Initialize count as 0;
count = 0
# Find the number groups and
# no. of rabbits in each group
for a in Map:
x = a
y = Map[a]
# Find number of groups and
# multiply them with number
# of rabbits in each group
if (y % (x + 1) == 0):
count = count + (y // (x + 1)) * (x + 1)
else:
count = count + ((y // (x + 1)) + 1) * (x + 1)
# count gives minimum number
# of rabbits in the forest
return count
# Driver code
arr = [2, 2, 0]
N = len(arr)
# Function Call
print(minNumberOfRabbits(arr, N))
# This code is contributed by divyesh072019
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
class GFG {
// Function to find the minimum
// number of rabbits in the forest
public static int minNumberOfRabbits(int[] answers,
int N)
{
// Initialize map
Dictionary<int, int> map
= new Dictionary<int, int>();
// Traverse array and map arr[i]
// to the number of occurrences
for (int a = 0; a < N; a++) {
if (map.ContainsKey(answers[a]))
map[answers[a]] += 1;
else
map.Add(answers[a], 1);
}
// Initialize count as 0;
int count = 0;
// Find the number groups and
// no. of rabbits in each group
for (int a = 0; a < map.Count; a++) {
int x = map.Keys.ElementAt(a);
int y = map[x];
// Find number of groups and
// multiply them with number
// of rabbits in each group
if (y % (x + 1) == 0) {
count = count + (y / (x + 1)) * (x + 1);
}
else
count
= count + ((y / (x + 1)) + 1) * (x + 1);
}
// count gives minimum number
// of rabbits in the forest
return count;
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 2, 2, 0 };
int N = arr.Length;
// Function Call
Console.WriteLine(minNumberOfRabbits(arr, N));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// JavaScript program for the above approach
// Function to find the minimum
// number of rabbits in the forest
function minNumberOfRabbits(answers, N)
{
// Initialize map
var map = new Map();
// Traverse array and map arr[i]
// to the number of occurrences
for (var a = 0; a < N; a++) {
if(map.has(answers[a]))
map.set(answers[a], map.get(answers[a])+1)
else
map.set(answers[a], 1)
}
// Initialize count as 0;
var count = 0;
// Find the number groups and
// no. of rabbits in each group
map.forEach((value, key) => {
var x = key;
var y = value;
// Find number of groups and
// multiply them with number
// of rabbits in each group
if (y % (x + 1) == 0)
count = count + parseInt(y / (x + 1)) * (x + 1);
else
count = count + (parseInt(y / (x + 1)) + 1) * (x + 1);
});
// count gives minimum number
// of rabbits in the forest
return count;
}
// Driver code
var arr = [2, 2, 0];
var N = arr.length;
// Function Call
document.write( minNumberOfRabbits(arr, N));
</script>
Producción
4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Otra solución es usar HashMap de los conteos y disminuir el conteo cada vez que se cumplen las mismas respuestas[i] . Si vuelven a aparecer las mismas respuestas[i] y el conteo es cero, restablezca el conteo con respuestas[i]+1 y agréguelo a la variable de respuesta. A continuación se muestran los pasos:
- Inicialice una cuenta variable con cero.
- Utilice un mapa mp desordenado.
- Recorra la array y haga lo siguiente:
- si las respuestas [i] se establecen en cero, establezca mp [respuestas [i]] = respuestas [i] + 1 y recuento = recuento + respuestas [i] + 1
- finalmente reste el conteo del mapa, mp[answers[i]]– ;
- devolver el cnt como respuesta.
C++
// C++ program for the above approach
#include <iostream>
#include <unordered_map>
using namespace std;
// Function to find the minimum
// number of rabbits in the forest
int minNumberOfRabbits(int answers[], int n)
{
// Initialize cnt variable
int count = 0;
// Initialize map
unordered_map<int, int> mp;
for (int i = 0; i < n; ++i) {
// Add to the count if not found or
// has exhausted the count of all the
// number of rabbits of same colour
if (mp[answers[i]] == 0) {
count += answers[i] + 1;
mp[answers[i]] = answers[i] + 1;
}
mp[answers[i]]--;
}
// count gives minimum number
// of rabbits in the forest
return count;
}
// Driver Code
int main()
{
int arr[] = { 10, 10, 0 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << minNumberOfRabbits(arr, N) << endl;
return 0;
}
// This code is contributed by Bhavna Soni - bhavna23
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find the minimum
// number of rabbits in the forest
static int minNumberOfRabbits(int[] answers, int n)
{
// Initialize cnt variable
int count = 0;
// Initialize map
HashMap<Integer, Integer> mp = new HashMap<Integer,Integer>();
for (int i = 0; i < n; ++i) {
// Add to the count if not found or
// has exhausted the count of all the
// number of rabbits of same colour
if (!mp.containsKey(answers[i]))
{
count += answers[i] + 1;
mp.put(answers[i],answers[i]+1);
}
if(mp.containsKey(answers[i]))
mp.put(answers[i],mp.get(answers[i])-1);
}
// count gives minimum number
// of rabbits in the forest
return count;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 10, 10, 0 };
int N = arr.length;
// Function Call
System.out.println(minNumberOfRabbits(arr, N));
}
}
// This code is contributed by Pushpesh Raj
Python3
# Python 3 program for the above approach
# Function to find the minimum
# number of rabbits in the forest
def minNumberOfRabbits(answers, n):
# Initialize cnt variable
count = 0
# Initialize map
mp = {}
for i in range(n):
# Add to the count if not found or
# has exhausted the count of all the
# number of rabbits of same colour
if (answers[i] not in mp):
count += answers[i] + 1
mp[answers[i]] = answers[i] + 1
mp[answers[i]] -= 1
# count gives minimum number
# of rabbits in the forest
return count
# Driver Code
if __name__ == "__main__":
arr = [10, 10, 0]
N = len(arr)
# Function Call
print(minNumberOfRabbits(arr, N))
# This code is contributed by ukasp.
Producción
12
Complejidad temporal: O(N)
Espacio auxiliar: O(N)