Given an array of integers arr of size N, the task is to find the minimum possible of the expression by choosing exactly K(? N) integers form given array arr. Let say if chosen elements are stored in array B (B1, B2, B3…..Bk) then value of expression:
Examples:
Input : arr[] = {2, 0, 9, 5}, k = 2
Output : 8
Let say, chosen elements are {2, 0}, then x = 8, which is minimum possibleInput : arr[] = {4, 21, 5, 3, 8}, k = 3
Output : 200
Approach :
The above expression can be simplified as:
So, all we need to do is select the k smallest elements from the array and solve the expression.
Below is the implementation of the above approach:
C++
// CPP program to find the minimum possible of the expression // by choosing exactly K(? N) integers form given array arr #include <bits/stdc++.h> using namespace std; // Function to find the minimum possible of the expression // by choosing exactly K(? N) integers form given array arr int minimumValue( int arr[], int n, int k) { // Sorting the array for least k element selection sort(arr, arr + n); int answer = 0; // Select first k elements from sorted array for ( int i = 0; i < k; i++) answer += arr[i] * arr[i]; // Return value of solved expression return answer * (2 * k - 2); } // Driver code int main() { int arr[] = { 4, 21, 5, 3, 8 }, k = 3; int n = sizeof (arr) / sizeof (arr[0]); // Function call cout << minimumValue(arr, n, k); return 0; } |
Java
// JAVA program to find the minimum possible of the expression // by choosing exactly K(? N) integers form given array arr import java.util.*; class GFG{ // Function to find the minimum possible of the expression // by choosing exactly K(? N) integers form given array arr static int minimumValue( int arr[], int n, int k) { // Sorting the array for least k element selection Arrays.sort(arr); int answer = 0 ; // Select first k elements from sorted array for ( int i = 0 ; i < k; i++) answer += arr[i] * arr[i]; // Return value of solved expression return answer * ( 2 * k - 2 ); } // Driver code public static void main(String[] args) { int arr[] = { 4 , 21 , 5 , 3 , 8 }, k = 3 ; int n = arr.length; // Function call System.out.print(minimumValue(arr, n, k)); } } // This code is contributed by Rajput-Ji |
Python3
# Python program to find the minimum # possible of the expression by choosing # exactly K(? N) integers form given array arr # Function to find the minimum # possible of the expression by # choosing exactly K(? N) integers # form given array arr def minimumValue(arr, n, k): # Sorting the array for least k element selection arr.sort(); answer = 0 ; # Select first k elements from sorted array for i in range (k): answer + = arr[i] * arr[i]; # Return value of solved expression return answer * ( 2 * k - 2 ); # Driver code if __name__ = = '__main__' : arr = [ 4 , 21 , 5 , 3 , 8 ]; k = 3 ; n = len (arr); # Function call print (minimumValue(arr, n, k)); # This code is contributed by Rajput-Ji |
C#
// C# program to find the minimum possible of the expression // by choosing exactly K(? N) integers form given array arr using System; class GFG{ // Function to find the minimum possible of the expression // by choosing exactly K(? N) integers form given array arr static int minimumValue( int []arr, int n, int k) { // Sorting the array for least k element selection Array.Sort(arr); int answer = 0; // Select first k elements from sorted array for ( int i = 0; i < k; i++) answer += arr[i] * arr[i]; // Return value of solved expression return answer * (2 * k - 2); } // Driver code public static void Main(String[] args) { int []arr = { 4, 21, 5, 3, 8 }; int k = 3; int n = arr.Length; // Function call Console.Write(minimumValue(arr, n, k)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program to find the minimum possible of the expression // by choosing exactly K(? N) integers form given array arr // Function to find the minimum possible of the expression // by choosing exactly K(? N) integers form given array arr function minimumValue(arr, n, k) { // Sorting the array for least k element selection arr.sort((a, b) => a - b); let answer = 0; // Select first k elements from sorted array for (let i = 0; i < k; i++) answer += arr[i] * arr[i]; // Return value of solved expression return answer * (2 * k - 2); } // Driver code let arr = [ 4, 21, 5, 3, 8 ], k = 3; let n = arr.length; // Function call document.write(minimumValue(arr, n, k)); // This code is contributed by Surbhi Tyagi. </script> |
200
Time Complexity: O(n * log n)
Auxiliary Space: O(1)
Another Efficient Method: This problem can be solved efficiently using a Priority Queue. As we have to find the k smallest elements from the array in order to solve the expression so we use a priority queue which will find the k smallest elements in O(n*log(k)) time complexity where n is the size of the array and k is the number of smallest elements needed. Once we get the k smallest elements in the priority queue we will use the simplified expression given above to find the minimum value.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum possible of the expression // by choosing exactly K(<= N) integers form given array arr int minimumValue( int arr[], int n, int k) { // Using a Priority Queue // to find k smallest elements priority_queue< int > heap1; for ( int i = 0; i < n; ++i) { // Insert elements into // the priority queue heap1.push(arr[i]); // If size of the priority // queue exceeds k then remove // the largest element from // the priority queue if (heap1.size() > k) { heap1.pop(); } } int answer = 0; // Using first k elements from priority queue // to find the minimum value for ( int i = 0; i < k; i++) { answer += heap1.top() * heap1.top(); heap1.pop(); } // Return value of solved expression return answer * (2 * k - 2); } // Driver code int main() { int arr[] = { 4, 21, 5, 3, 8 }, k = 3; int n = sizeof (arr) / sizeof (arr[0]); // Function call cout << minimumValue(arr, n, k); return 0; } // This code is contributed by Pushpesh Raj |
Java
// Java code to implement the approach import java.util.*; class GFG { // Function to find the minimum possible of the // expression by choosing exactly K(<= N) integers form // given array arr static int minimumValue( int [] arr, int n, int k) { // Using a Priority Queue // to find k smallest elements PriorityQueue<Integer> heap1 = new PriorityQueue<Integer>( Collections.reverseOrder()); for ( int i = 0 ; i < n; ++i) { // Insert elements into // the priority queue heap1.add(arr[i]); // If size of the priority // queue exceeds k then remove // the largest element from // the priority queue if (heap1.size() > k) { heap1.poll(); } } int answer = 0 ; // Using first k elements from priority queue // to find the minimum value for (var i = 0 ; i < k; i++) { answer += heap1.peek() * heap1.peek(); heap1.poll(); } // Return value of solved expression return answer * ( 2 * k - 2 ); } // Driver code public static void main(String[] args) { int [] arr = { 4 , 21 , 5 , 3 , 8 }; int k = 3 ; int n = arr.length; // Function call System.out.println(minimumValue(arr, n, k)); } } // This code is contributed by phasing17 |
Python3
# Python3 code to implement the approach # Function to find the minimum possible of the expression # by choosing exactly K(<= N) integers form given array arr def minimumValue(arr, n, k): # Using a Priority Queue # to find k smallest elements heap1 = []; for i in range (n): # Insert elements into # the priority queue heap1.append(arr[i]); heap1.sort(reverse = True ) # If size of the priority # queue exceeds k then remove # the largest element from # the priority queue if ( len (heap1) > k): heap1.pop( 0 ); answer = 0 ; # Using first k elements from priority queue # to find the minimum value for i in range (k): answer + = heap1[ 0 ] * heap1[ 0 ]; heap1.pop( 0 ); # Return value of solved expression return answer * ( 2 * k - 2 ); # Driver code arr = [ 4 , 21 , 5 , 3 , 8 ] k = 3 ; n = len (arr); # Function call print (minimumValue(arr, n, k)); # This code is contributed by phasing17 |
C#
// C# code to implement the approach using System; using System.Collections.Generic; class GFG { // Function to find the minimum possible of the // expression by choosing exactly K(<= N) integers form // given array arr static int minimumValue( int [] arr, int n, int k) { // Using a Priority Queue // to find k smallest elements List< int > heap1 = new List< int >(); for ( int i = 0; i < n; ++i) { // Insert elements into // the priority queue heap1.Add(arr[i]); heap1.Sort(); heap1.Reverse(); // If size of the priority // queue exceeds k then remove // the largest element from // the priority queue if (heap1.Count > k) { heap1.RemoveAt(0); } } int answer = 0; // Using first k elements from priority queue // to find the minimum value for ( var i = 0; i < k; i++) { answer += heap1[0] * heap1[0]; heap1.RemoveAt(0); } // Return value of solved expression return answer * (2 * k - 2); } // Driver code public static void Main( string [] args) { int [] arr = { 4, 21, 5, 3, 8 }; int k = 3; int n = arr.Length; // Function call Console.WriteLine(minimumValue(arr, n, k)); } } // This code is contributed by phasing17 |
Javascript
// JS code to implement the approach // Function to find the minimum possible of the expression // by choosing exactly K(<= N) integers form given array arr function minimumValue(arr, n, k) { // Using a Priority Queue // to find k smallest elements let heap1 = []; for ( var i = 0; i < n; ++i) { // Insert elements into // the priority queue heap1.push(arr[i]); heap1.sort( function (a, b) { return a < b}) // If size of the priority // queue exceeds k then remove // the largest element from // the priority queue if (heap1.length > k) { heap1.shift(); } } let answer = 0; // Using first k elements from priority queue // to find the minimum value for ( var i = 0; i < k; i++) { answer += heap1[0] * heap1[0]; heap1.shift(); } // Return value of solved expression return answer * (2 * k - 2); } // Driver code let arr = [4, 21, 5, 3, 8 ] let k = 3; let n = arr.length; // Function call console.log(minimumValue(arr, n, k)); // This code is contributed by phasing17 |
200
Time Complexity: O(k+nlog(k)) where n is the size of the array and k is the given number of elements to choose from.
Auxiliary Space: O(k) since the priority queue at any time holds k elements.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!