Dada una array arr[] de enteros de tamaño N donde cada elemento puede estar en el rango [1, M] y dos enteros X y K . La tarea es encontrar K números posibles en el rango [1, M] de modo que el promedio de todos los números (N + K) sea igual a X. Si hay múltiples respuestas válidas, cualquiera es aceptable.
Ejemplos:
Entrada: arr[] = {3, 2, 4, 3}, M = 6, K = 2, X = 4
Salida: 6 6
Explicación: La media de todos los elementos es (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4.Entrada: arr[] = {1}, M = 8, K = 1, X = 4
Salida: 7
Explicación: La media de todos los elementos es (1 + 7) / 2 = 4.Entrada: arr[] = {1, 2, 3, 4}, M = 6, K = 4, X = 6
Salida: []
Explicación: Es imposible que la media sea 6 sin importar cuáles sean los 4 elementos faltantes .
Enfoque: El enfoque se basa en la siguiente observación matemática. Si la suma total esperada después de agregar M elementos es tal que la suma de los M elementos agregados debe ser menor que M o mayor que K*M, entonces no hay solución posible. De lo contrario, siempre hay una solución posible.
- Encuentre la suma de los elementos que faltan (Y), es decir = X*(K + N) – sum(arr).
- Si es menor que K o mayor que K*M , no se puede crear la array. Así que devuelve una array vacía.
- De lo contrario, trate de dividir equitativamente el valor Y en K elementos, es decir, asigne a todos los K elementos el valor Y/K.
- si aún queda algún valor por asignar, luego de asignar todos los elementos por igual, el valor que queda será = (Y%K). Entonces agregue 1 a (Y%K) elementos de la nueva array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
// Function to get the missing elements
vector<int> missing(vector<int>& arr,
int M, int X, int K)
{
int N = arr.size(),
sum = accumulate(arr.begin(),
arr.end(), 0),
newsum = 0;
newsum = X * (K + N) - sum;
// If this newsum is less than M
// or greater than K*M then
// no array can be created.
if (newsum < K || newsum > K * M)
return {};
int mod = newsum % K;
vector<int> ans(K, newsum / K);
for (int i = 0; i < mod; i++)
ans[i] += 1;
return ans;
}
// Driver code
int main()
{
vector<int> arr{ 3, 2, 4, 3 };
int X = 4;
int K = 2;
int M = 6;
// Vector to store resultant list
vector<int> ans = missing(arr, M, X, K);
for (auto i : ans)
cout << i << " ";
return 0;
}
Java
// Java code to implement above approach
import java.util.*;
class GFG{
// Function to get the missing elements
static int []missing(int []arr,
int M, int X, int K)
{
int N = arr.length,
sum = accumulate(arr,0,N),
newsum = 0;
newsum = X * (K + N) - sum;
// If this newsum is less than M
// or greater than K*M then
// no array can be created.
if (newsum < K || newsum > K * M)
return new int[]{};
int mod = newsum % K;
int []ans = new int[K];
Arrays.fill(ans, newsum / K);
for (int i = 0; i < mod; i++)
ans[i] += 1;
return ans;
}
static int accumulate(int[] arr, int start, int end){
int sum=0;
for(int i= 0; i < arr.length; i++)
sum+=arr[i];
return sum;
}
// Driver code
public static void main(String[] args)
{
int[]arr = { 3, 2, 4, 3 };
int X = 4;
int K = 2;
int M = 6;
// Vector to store resultant list
int []ans = missing(arr, M, X, K);
for (int i : ans)
System.out.print(i+ " ");
}
}
// This code is contributed by shikhasingrajput
Python3
# Python code for the above approach # Function to get the missing elements def missing(arr, M, X, K): N = len(arr) sum = 0 for i in range(len(arr)): sum += arr[i] newsum = 0 newsum = X * (K + N) - sum # If this newsum is less than M # or greater than K*M then # no array can be created. if (newsum < K or newsum > K * M): return [] mod = newsum % K ans = [newsum // K] * K for i in range(mod): ans[i] += 1 return ans # Driver code arr = [3, 2, 4, 3] X = 4 K = 2 M = 6 # Vector to store resultant list ans = missing(arr, M, X, K) for i in ans: print(i, end=" ") # This code is contributed by gfgking
C#
// C# code to implement above approach
using System;
class GFG {
// Function to get the missing elements
static int[] missing(int[] arr, int M, int X, int K)
{
int N = arr.Length, sum = accumulate(arr, 0, N),
newsum = 0;
newsum = X * (K + N) - sum;
// If this newsum is less than M
// or greater than K*M then
// no array can be created.
if (newsum < K || newsum > K * M)
return new int[] {};
int mod = newsum % K;
int[] ans = new int[K];
Array.Fill(ans, newsum / K);
for (int i = 0; i < mod; i++)
ans[i] += 1;
return ans;
}
static int accumulate(int[] arr, int start, int end)
{
int sum = 0;
for (int i = 0; i < arr.Length; i++)
sum += arr[i];
return sum;
}
// Driver code
public static void Main(string[] args)
{
int[] arr = { 3, 2, 4, 3 };
int X = 4;
int K = 2;
int M = 6;
// Vector to store resultant list
int[] ans = missing(arr, M, X, K);
foreach(int i in ans) Console.Write(i + " ");
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript code for the above approach
// Function to get the missing elements
function missing(arr,
M, X, K) {
let N = arr.length;
let sum = 0;
for (let i = 0; i < arr.length; i++) {
sum += arr[i];
}
newsum = 0;
newsum = X * (K + N) - sum;
// If this newsum is less than M
// or greater than K*M then
// no array can be created.
if (newsum < K || newsum > K * M)
return [];
let mod = newsum % K;
let ans = new Array(K).fill(Math.floor(newsum / K))
for (let i = 0; i < mod; i++)
ans[i] += 1;
return ans;
}
// Driver code
let arr = [3, 2, 4, 3];
let X = 4;
let K = 2;
let M = 6;
// Vector to store resultant list
let ans = missing(arr, M, X, K);
for (let i of ans)
document.write(i + " ");
// This code is contributed by Potta Lokesh
</script>
6 6
Complejidad Temporal: O(N)
Espacio Auxiliar: O(1) Cuando no se considera el espacio de la lista resultante
Publicación traducida automáticamente
Artículo escrito por rishabhbatra53 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA