Find K numbers with sum equal to N and sum of their squares maximized

0 0 3 minutes read

Given two integers N and K, the task is to find K numbers(A₁, A₂, …, A_K) such that ?_i=1^KA_i is equal to N and ?_i=1^KA_i² 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 1² + 2² 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, (a² + b²) is always less than 1 + (a + b – 1)².
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>

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 zambiatek!