Dado un número N de palos de diferentes longitudes en una array arr , la tarea es determinar la suma de la cantidad de palos que quedan después de cada iteración. En cada iteración, corte la longitud del palo más corto de los palos restantes.
Ejemplos:
Input: N = 6, arr = {5, 4, 4, 2, 2, 8}
Output: 7
Explanation:
Iteration 1:
Initial arr = {5, 4, 4, 2, 2, 8}
Shortest stick = 2
arr with reduced length = {3, 2, 2, 0, 0, 6}
Remaining sticks = 4
Iteration 2:
arr = {3, 2, 2, 4}
Shortest stick = 2
Left stick = 2
Iteration 3:
arr = {1, 2}
Shortest stick = 1
Left stick = 1
Iteration 4:
arr = {1}
Min length = 1
Left stick = 0
Input: N = 8, arr = {1, 2, 3, 4, 3, 3, 2, 1}
Output: 11
Enfoque: el enfoque para resolver este problema es ordenar la array y luego encontrar el número de palos de longitud mínima que tienen la misma longitud mientras se recorre y actualizar la suma en consecuencia en cada paso y al final devolver la suma.
C++
// C++ program to find the sum of
// remaining sticks after each iterations
#include <bits/stdc++.h>
using namespace std;
// Function to calculate
// sum of remaining sticks
// after each iteration
int sum(vector<int> &arr, int n)
{
int sum = 0;
sort(arr.begin(),arr.end());
int prev=0,count=1,s=arr.size();
int i=1;
while(i<arr.size()){
if(arr[i]==arr[prev]){
count++;
}else{
prev=i;
sum+=s-count;
s-=count;
count=1;
}
i++;
}
return sum;
}
// Driver code
int main()
{
int n = 6;
vector<int> ar{ 5, 4, 4, 2, 2, 8 };
int ans = sum(ar, n);
cout << ans << '\n';
return 0;
}
Java
// Java program to find the sum of
// remaining sticks after each iterations
import java.io.*;
import java.util.*;
class GFG{
// Function to calculate
// sum of remaining sticks
// after each iteration
public static int sum(int arr[], int n)
{
int sum = 0;
Arrays.sort(arr);
int prev = 0, count = 1, s = n;
int i = 1;
while (i < n)
{
if (arr[i] == arr[prev])
{
count++;
}
else
{
prev = i;
sum += s - count;
s -= count;
count = 1;
}
i++;
}
return sum;
}
// Driver code
public static void main(String[] args)
{
int n = 6;
int ar[] = { 5, 4, 4, 2, 2, 8 };
int ans = sum(ar, n);
System.out.println(ans);
}
}
// This code is contributed by Manu Pathria
Python3
# Python program to find the sum of # remaining sticks after each iterations # Function to calculate # sum of remaining sticks # after each iteration def sum(arr, n): sum = 0 arr.sort() prev, count, s = 0, 1, n i = 1 while (i < n): if (arr[i] == arr[prev]): count += 1 else: prev = i sum += s - count s -= count count = 1 i += 1 return sum # Driver code n = 6 ar = [ 5, 4, 4, 2, 2, 8 ] ans = sum(ar, n) print(ans) # This code is contributed by shinjanpatra
C#
// C# program to find the sum of
// remaining sticks after each iterations
using System;
using System.Collections.Generic;
class GFG
{
// Function to calculate
// sum of remaining sticks
// after each iteration
public static int sum(int[] arr, int n)
{
int sum = 0;
Array.Sort(arr);
int prev = 0, count = 1, s = n;
int i = 1;
while (i < n)
{
if (arr[i] == arr[prev])
{
count++;
}
else
{
prev = i;
sum += s - count;
s -= count;
count = 1;
}
i++;
}
return sum;
}
// Driver code
public static void Main (String[] args)
{
int n = 6;
int[] ar = { 5, 4, 4, 2, 2, 8 };
int ans = sum(ar, n);
Console.WriteLine(ans);
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// Java Script program to find the sum of
// remaining sticks after each iterations
// Function to calculate
// sum of remaining sticks
// after each iteration
function sum(arr,n)
{
let sum = 0;
arr.sort();
let prev = 0, count = 1, s = n;
let i = 1;
while (i < n)
{
if (arr[i] == arr[prev])
{
count++;
}
else
{
prev = i;
sum += s - count;
s -= count;
count = 1;
}
i++;
}
return sum;
}
// Driver code
let n = 6;
let ar = [ 5, 4, 4, 2, 2, 8 ];
let ans = sum(ar, n);
document.write(ans);
// This code is contributed by manoj
</script>
Complejidad de tiempo : O(Nlog(N)) donde N es el número de palos.
Otro enfoque:
- Almacene la frecuencia de las longitudes de los palos en un mapa
- En cada iteración,
- Encuentre la frecuencia del palo de longitud mínima
- Disminuya la frecuencia del palo de longitud mínima de la frecuencia de cada palo
- Agregue el recuento de palos distintos de cero al palo resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the sum of
// remaining sticks after each iterations
#include <bits/stdc++.h>
using namespace std;
// Function to calculate
// sum of remaining sticks
// after each iteration
int sum(int ar[], int n)
{
map<int, int> mp;
// storing frequency of stick length
for (int i = 0; i < n; i++) {
mp[ar[i]]++;
}
int sum = 0;
for (auto p : mp) {
n -= p.second;
sum += n;
}
return sum;
}
// Driver code
int main()
{
int n = 6;
int ar[] = { 5, 4, 4, 2, 2, 8 };
int ans = sum(ar, n);
cout << ans << '\n';
return 0;
}
Java
// Java program to find the sum of
// remaining sticks after each iterations
import java.util.HashMap;
import java.util.Map;
class GFG
{
// Function to calculate
// sum of remaining sticks
// after each iteration
static int sum(int ar[], int n)
{
HashMap<Integer,
Integer> mp = new HashMap<>();
for (int i = 0; i < n; i++)
{
mp.put(ar[i], 0);
}
// storing frequency of stick length
for (int i = 0; i < n; i++)
{
mp.put(ar[i], mp.get(ar[i]) + 1) ;
}
int sum = 0;
for(Map.Entry p : mp.entrySet())
{
n -= (int)p.getValue();
sum += n;
}
return sum;
}
// Driver code
public static void main (String[] args)
{
int n = 6;
int ar[] = { 5, 4, 4, 2, 2, 8 };
int ans = sum(ar, n);
System.out.println(ans);
}
}
// This code is contributed by kanugargng
Python3
# Python proagram to find sum # of remaining sticks # Function to calculate # sum of remaining sticks # after each iteration def sum(ar, n): mp = dict() for i in ar: if i in mp: mp[i]+= 1 else: mp[i] = 1 mp = sorted(list(mp.items())) sum = 0 for pair in mp: n-= pair[1] sum+= n return sum # Driver code def main(): n = 6 ar = [5, 4, 4, 2, 2, 8] ans = sum(ar, n) print(ans) main()
C#
// C# program to find the sum of
// remaining sticks after each iterations
using System;
using System.Collections.Generic;
class GFG
{
// Function to calculate
// sum of remaining sticks
// after each iteration
static int sum(int []ar, int n)
{
SortedDictionary<int,
int> mp = new SortedDictionary<int,
int>();
// storing frequency of stick length
for (int i = 0; i < n; i++)
{
if(!mp.ContainsKey(ar[i]))
mp.Add(ar[i], 0);
else
mp[ar[i]] = 0;
}
// storing frequency of stick length
for (int i = 0; i < n; i++)
{
if(!mp.ContainsKey(ar[i]))
mp.Add(ar[i], 1);
else
mp[ar[i]] = ++mp[ar[i]];
}
int sum = 0;
foreach(KeyValuePair<int, int> p in mp)
{
n -= p.Value;
sum += n;
}
return sum;
}
// Driver code
public static void Main (String[] args)
{
int n = 6;
int []ar = { 5, 4, 4, 2, 2, 8 };
int ans = sum(ar, n);
Console.WriteLine(ans);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to find the sum of
// remaining sticks after each iterations
// Function to calculate
// sum of remaining sticks
// after each iteration
function sum(ar, n)
{
let mp = new Map();
for (let i = 0; i < n; i++)
{
mp.set(ar[i], 0);
}
// storing frequency of stick length
for (let i = 0; i < n; i++)
{
mp.set(ar[i], mp.get(ar[i]) + 1);
}
mp = new Map([...mp].sort((a, b) => String(a[0]).localeCompare(b[0])))
let sum = 0;
for (let p of mp)
{
n -= p[1]
sum += n;
}
return sum;
}
// Driver code
let n = 6;
let ar = [5, 4, 4, 2, 2, 8];
let ans = sum(ar, n);
document.write(ans + '<br>');
// This code is contributed by _saurabh_jaiswal.
</script>
Producción:
7
Complejidad temporal:
donde N es el número de palos
Publicación traducida automáticamente
Artículo escrito por everything_is_possible y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA