Given an array arr[] of integers of size N where each element can be in the range [1, M], and two integers X and K. The task is to find K possible numbers in range [1, M] such that the average of all the (N + K) numbers is equal to X. If there are multiple valid answers, any one is acceptable.
Examples:
Input: arr[] = {3, 2, 4, 3}, M = 6, K = 2, X = 4
Output: 6 6
Explanation: The mean of all elements is (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4.Input: arr[] = {1}, M = 8, K = 1, X = 4
Output: 7
Explanation: The mean of all elements is (1 + 7) / 2 = 4.Input: arr[] = {1, 2, 3, 4}, M = 6, K = 4, X = 6
Output: []
Explanation: It is impossible for the mean to be 6 no matter what the 4 missing elements are.
Approach: The approach is based on the following mathematical observation. If the total expected sum after adding M elements is such that the sum of the M elements added needs to be less than M or greater than K*M then no solution is possible. Otherwise, there is always a possible solution.
- Find the sum of missing elements(Y), that is = X*(K + N) – sum(arr).
- If this is less than K or greater than K*M then the array cannot be created. So return an empty array.
- Otherwise, try to equally divide the value Y in K elements, i.e assign all the K elements with value Y/K.
- if still some value remains to be assigned then after assigning every element equally, the value left will be = (Y%K). So add 1 to (Y%K) elements of the new array.
Below is the implementation of the above approach:
C++
// C++ code to implement above approach#include <bits/stdc++.h>using namespace std;// Function to get the missing elementsvector<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 codeint 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 approachimport java.util.*;class GFG{// Function to get the missing elementsstatic 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 codepublic 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 elementsdef 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 codearr = [3, 2, 4, 3]X = 4K = 2M = 6# Vector to store resultant listans = missing(arr, M, X, K)for i in ans: print(i, end=" ")# This code is contributed by gfgking |
C#
// C# code to implement above approachusing 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> |
Output
6 6
Time Complexity: O(N)
Auxiliary Space: O(1) When space of the resultant list is not considered
Share your thoughts in the comments
