Find the deleted value from the array when average of original elements is given
Given an array of length N + K. Also given the average avg of all the elements of the array. If an element that appears exactly K time got removed from the array (all the occurrences) and the resultant array is given, the task is to find the element X. Note that if X is not an integer then print -1.
Examples:
Input: arr[] = {2, 7, 3}, K = 3, avg = 4
Output: 4
The original array was {2, 7, 3, 4, 4, 4}
where 4 which occurred thrice was deleted.
(2 + 7 + 3 + 4 + 4 + 4) / 6 = 4Input: arr[] = {5, 2, 3}, K = 4, avg = 7;
Output: -1
The required element is 9.75 which is not an integer.
Approach:
- Find the sum of the array elements and store it in a variable sum.
- Since X appeared K times then the sum of the original array will be sumOrg = sum + (X * K).
- And the average is given to be avg i.e. avg = sumOrg / (N + K).
- Now, X can be easily calculated as X = ((avg * (N + K)) – sum) / K
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the missing element int findMissing( int arr[], int n, int k, int avg) { // Find the sum of the array elements int sum = 0; for ( int i = 0; i < n; i++) { sum += arr[i]; } // The numerator and the denominator // of the equation int num = (avg * (n + k)) - sum; int den = k; // If not divisible then X is // not an integer // it is a floating point number if (num % den != 0) return -1; // Return X return (num / den); } // Driver code int main() { int k = 3, avg = 4; int arr[] = { 2, 7, 3 }; int n = sizeof (arr) / sizeof ( int ); cout << findMissing(arr, n, k, avg); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return the missing element static int findMissing( int arr[], int n, int k, int avg) { // Find the sum of the array elements int sum = 0 ; for ( int i = 0 ; i < n; i++) { sum += arr[i]; } // The numerator and the denominator // of the equation int num = (avg * (n + k)) - sum; int den = k; // If not divisible then X is // not an integer // it is a floating point number if (num % den != 0 ) return - 1 ; // Return X return ( int )(num / den); } // Driver code public static void main (String[] args) { int k = 3 , avg = 4 ; int arr[] = { 2 , 7 , 3 }; int n = arr.length; System.out.println(findMissing(arr, n, k, avg)); } } // This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach # Function to return the missing element def findMissing(arr, n, k, avg): # Find the sum of the array elements sum = 0 ; for i in range (n): sum + = arr[i]; # The numerator and the denominator # of the equation num = (avg * (n + k)) - sum ; den = k; # If not divisible then X is # not an integer # it is a floating point number if (num % den ! = 0 ): return - 1 ; # Return X return ( int )(num / den); # Driver code k = 3 ; avg = 4 ; arr = [ 2 , 7 , 3 ] ; n = len (arr); print (findMissing(arr, n, k, avg)); # This code is contributed by 29AjayKumar |
C#
// C# implementation of above approach using System; class GFG { // Function to return the missing element static int findMissing( int []arr, int n, int k, int avg) { // Find the sum of the array elements int sum = 0; for ( int i = 0; i < n; i++) { sum += arr[i]; } // The numerator and the denominator // of the equation int num = (avg * (n + k)) - sum; int den = k; // If not divisible then X is // not an integer // it is a floating point number if (num % den != 0) return -1; // Return X return ( int )(num / den); } // Driver code public static void Main (String[] args) { int k = 3, avg = 4; int []arr = { 2, 7, 3 }; int n = arr.Length; Console.WriteLine(findMissing(arr, n, k, avg)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript implementation of the // above approach // Function to return the missing element function findMissing(arr, n, k, avg) { // Find the sum of the array elements var sum = 0; for ( var i = 0; i < n; i++) { sum += arr[i]; } // The numerator and the denominator // of the equation var num = (avg * (n + k)) - sum; var den = k; // If not divisible then X is // not an integer // it is a floating point number if (num % den != 0) return -1; // Return X return (Math.floor(num / den)); } // Driver code var k = 3; var avg = 4; var arr = [ 2, 7, 3 ]; var n = arr.length; document.write(findMissing(arr, n, k, avg)); // This code is contributed by ShubhamSingh10 </script> |
Output:
4
Time Complexity: O(n), where n is the size of the given array.
Auxiliary Space: O(1)