Dados dos números enteros N , K y una array arr[] que consta de números enteros positivos. La tarea es encontrar cualquier arreglo posible de tamaño N tal que la media de arr[] y el arreglo a encontrar juntos sea K .
Ejemplos:
Entrada: arr[] = {1, 5, 6}, N = 4, K = 3
Salida: {1, 2, 3, 3}
Explicación: Media de {1, 5, 6} y {1, 2, 3 , 3} juntos es lo siguiente:
(1 + 5 + 6 + 1 + 2 + 3 + 3) / (3+4) = 3.
Por lo tanto, {1, 2, 3, 3} es un arreglo posible para hacer la media = 3.Entrada: arr[] = {7, 8, 6}, N = 2, K = 3
Salida: No es posible
Enfoque: este problema se puede resolver usando conceptos simples de promedio del sistema numérico . Digamos que sumArr sea la suma de la array new_arr[] y M sea el tamaño de new_arr[] . Entonces, de acuerdo con el concepto de promedio, la ecuación se puede formar como:
(sumArr + X) / (N+M) = K , donde X es la suma de la array requerida.
X = K * (N + M) – sumaArr.
Por lo tanto, la suma de la array requerida debe ser X para que la media sea igual a K. Si X es menor que N , entonces no hay forma de formar la array.
La forma más sencilla de formar la array requerida es
1, 1, 1, …(M-1 veces), X-(M-1)
.
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;
// Find the required array such that mean of both
// the arrays is equal to K
vector<int> findArray(vector<int> arr,
int N, int K)
{
// To store sum of elements in arr[]
int sumArr = 0;
int M = int(arr.size());
// Iterate to find sum
for (int i = 0; i < M; i++) {
sumArr += arr[i];
}
// According to the formula derived above
int X = K * (N + M) - sumArr;
// If requiredSum if less than N
if (X < N) {
cout << "Not Possible";
return {};
}
// Otherwise create an array to store answer
vector<int> res(N);
// Putting all 1s till N-1
for (int i = 0; i < N - 1; i++) {
res[i] = 1;
}
res[N - 1] = X - (N - 1);
// Return res as the final result
return res;
}
// Driver Code
int main()
{
vector<int> arr = { 1, 5, 6 };
int N = 4, K = 3;
vector<int> ans = findArray(arr, N, K);
for (int i = 0; i < ans.size(); i++)
cout << ans[i] << " ";
}
Java
// Java program for the above approach
public class GFG {
// Find the required array such that mean of both
// the arrays is equal to K
static void findArray(int []arr,
int N, int K)
{
// To store sum of elements in arr[]
int sumArr = 0;
int M = arr.length;
// Iterate to find sum
for (int i = 0; i < M; i++) {
sumArr += arr[i];
}
// According to the formula derived above
int X = K * (N + M) - sumArr;
// If requiredSum if less than N
if (X < N) {
System.out.println("Not Possible");
}
// Otherwise create an array to store answer
int []res = new int[N];
// Putting all 1s till N-1
for (int i = 0; i < N - 1; i++) {
res[i] = 1;
}
res[N - 1] = X - (N - 1);
// Return res as the final result
for (int i = 0; i < res.length; i++)
System.out.print(res[i] + " ");
}
// Driver Code
public static void main (String[] args)
{
int []arr = { 1, 5, 6 };
int N = 4, K = 3;
findArray(arr, N, K);
}
}
// This code is contributed by AnkThon
Python3
# python program for the above approach
# Find the required array such that mean of both
# the arrays is equal to K
def findArray(arr, N, K):
# To store sum of elements in arr[]
sumArr = 0
M = len(arr)
# Iterate to find sum
for i in range(0, M):
sumArr += arr[i]
# According to the formula derived above
X = K * (N + M) - sumArr
# If requiredSum if less than N
if (X < N):
print("Not Possible")
return []
# Otherwise create an array to store answer
res = [0 for _ in range(N)]
# Putting all 1s till N-1
for i in range(0, N-1):
res[i] = 1
res[N - 1] = X - (N - 1)
# Return res as the final result
return res
# Driver Code
if __name__ == "__main__":
arr = [1, 5, 6]
N = 4
K = 3
ans = findArray(arr, N, K)
for i in range(0, len(ans)):
print(ans[i], end=" ")
# This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
public class GFG {
// Find the required array such that mean of both
// the arrays is equal to K
static void findArray(int []arr,
int N, int K)
{
// To store sum of elements in arr[]
int sumArr = 0;
int M = arr.Length;
// Iterate to find sum
for (int i = 0; i < M; i++) {
sumArr += arr[i];
}
// According to the formula derived above
int X = K * (N + M) - sumArr;
// If requiredSum if less than N
if (X < N) {
Console.WriteLine("Not Possible");
}
// Otherwise create an array to store answer
int []res = new int[N];
// Putting all 1s till N-1
for (int i = 0; i < N - 1; i++) {
res[i] = 1;
}
res[N - 1] = X - (N - 1);
// Return res as the final result
for (int i = 0; i < res.Length; i++)
Console.Write(res[i] + " ");
}
// Driver Code
public static void Main (string[] args)
{
int []arr = { 1, 5, 6 };
int N = 4, K = 3;
findArray(arr, N, K);
}
}
// This code is contributed by AnkThon
Javascript
<script>
// Javascript program for the above approach
// Find the required array such that mean of both
// the arrays is equal to K
function findArray(arr, N, K) {
// To store sum of elements in arr[]
let sumArr = 0;
let M = (arr.length);
// Iterate to find sum
for (let i = 0; i < M; i++) {
sumArr += arr[i];
}
// According to the formula derived above
let X = K * (N + M) - sumArr;
// If requiredSum if less than N
if (X < N) {
document.write("Not Possible");
return [];
}
// Otherwise create an array to store answer
let res = new Array(N);
// Putting all 1s till N-1
for (let i = 0; i < N - 1; i++) {
res[i] = 1;
}
res[N - 1] = X - (N - 1);
// Return res as the final result
return res;
}
// Driver Code
let arr = [1, 5, 6];
let N = 4, K = 3;
let ans = findArray(arr, N, K);
for (let i = 0; i < ans.length; i++)
document.write(ans[i] + " ");
// This code is contributed by gfgking.
</script>
1 1 1 6
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por bunny09262002 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA