Given two integers N and K, the task is to find K numbers(A1, A2, …, AK) such that ?i=1KAi is equal to N and ?i=1KAi2 is maximum.
Examples:
Input: N = 3, K = 2
Output: 1 2
Explanation: The two numbers are 1 and 2 as their sum is equal to N and 12 + 22 is maximum.
Input: N = 10, K = 3
Output: 1 8 1
Approach: The idea is to take number 1, K – 1 times and number N – K + 1 once. The sum of these numbers is equal to N and sum of squares of these numbers is always maximum. For any two non-negative numbers a and b, (a2 + b2) is always less than 1 + (a + b – 1)2.
Below is the implementation of the above approach:
C++
// C++ program to find K numbers// with sum equal to N and the// sum of their squares maximized#include <bits/stdc++.h>using namespace std;// Function that prints the// required K numbersvoid printKNumbers(int N, int K){ // Print 1, K-1 times for (int i = 0; i < K - 1; i++) cout << 1 << " "; // Print (N-K+1) cout << (N - K + 1);}// Driver Codeint main(){ int N = 10, K = 3; printKNumbers(N, K); return 0;} |
Java
// Java program to find K numbers// with sum equal to N and the// sum of their squares maximizedclass GFG{// Function that prints the// required K numbersstatic void printKNumbers(int N, int K){ // Print 1, K-1 times for(int i = 0; i < K - 1; i++) System.out.print(1 + " "); // Print (N - K + 1) System.out.print(N - K + 1);}// Driver Codepublic static void main(String[] args){ int N = 10, K = 3; printKNumbers(N, K);}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program to find K numbers # with a sum equal to N and the # sum of their squares maximized # Function that prints the # required K numbers def printKNumbers(N, K): # Print 1, K-1 times for i in range(K - 1): print(1, end = ' ') # Print (N-K+1) print(N - K + 1) # Driver code if __name__=='__main__': (N, K) = (10, 3) printKNumbers(N, K) # This code is contributed by rutvik_56 |
C#
// C# program to find K numbers// with sum equal to N and the// sum of their squares maximizedusing System; class GFG{// Function that prints the// required K numbersstatic void printKNumbers(int N, int K){ // Print 1, K-1 times for(int i = 0; i < K - 1; i++) Console.Write(1 + " "); // Print (N - K + 1) Console.Write(N - K + 1);}// Driver codepublic static void Main(String[] args) { int N = 10, K = 3; printKNumbers(N, K);}}// This code is contributed by shivanisinghss2110 |
Javascript
<script> // Javascript program to find K numbers // with sum equal to N and the // sum of their squares maximized // Function that prints the // required K numbers function printKNumbers(N, K) { // Print 1, K-1 times for (let i = 0; i < K - 1; i++) document.write(1 + " "); // Print (N-K+1) document.write(N - K + 1); } let N = 10, K = 3; printKNumbers(N, K); </script> |
Output:
1 1 8
Time Complexity: O(K)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Find More to that Topic: geeksforgeeks.org/find-k-numbers-with-sum-equal-to-n-and-sum-of-their-squares-maximized/ […]