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 numbers void 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 Code int 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 maximized class GFG{ // Function that prints the // required K numbers static 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 Code public 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 maximized using System; class GFG{ // Function that prints the // required K numbers static 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 code public 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> |
1 1 8
Time Complexity: O(K)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!