Given two integers S and N, the task is to find the maximum possible sum of squares of N integers that can be placed in a stack such that the following properties are satisfied:
- The integer at the top of the stack should not be smaller than the element immediately below it.
- All stack elements should be in the range [1, 9].
- The Sum of stack elements should be exactly equal to S.
If it is impossible to obtain such an arrangement, print -1.
Examples:
Input: S = 12, N = 3
Output: 86
Explanation:
Stack arrangement [9, 2, 1] generates the sum 12 (= S), thus, satisfying the properties.
Therefore, maximum possible sum of squares = 9 * 9 + 2 * 2 + 1 * 1= 81 + 4 + 1 = 86Input: S = 11, N = 1
Output: -1
Approach: Follow the steps below to solve the problem:
- Check if S is valid, i.e. if it lies within the range [N, 9 * N].
- Initialize a variable, say res to store the maximum sum of squares of stack elements.
- The minimum value of an integer in the stack can be 1, so initialize all the stack elements with 1. Hence, deduct N from S.
- Now, check the number of integers having a value of more than 1. For this, add 8 (if it is possible) to the integers starting from the base of the stack and keep on adding it until S > 0.
- In the end, add S % 8 to the current integer and fill all remaining stack elements with 1.
- Finally, add the sum of squares of stack elements.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum// sum of squares of stack elementsvoid maxSumOfSquares(int N, int S){ // Stores the sum ofsquares // of stack elements int res = 0; // Check if sum is valid if (S < N || S > 9 * N) { cout << (-1); return; } // Initialize all stack // elements with 1 S = S - N; // Stores the count the // number of stack elements // not equal to 1 int c = 0; // Add the sum of squares // of stack elements not // equal to 1 while (S > 0) { c++; if (S / 8 > 0) { res += 9 * 9; S -= 8; } else { res += (S + 1) * (S + 1); break; } } // Add 1 * 1 to res as the // remaining stack elements // are 1 res = res + (N - c); // Print the result cout << (res);}// Driver Codeint main(){ int N = 3; int S = 12; // Function call maxSumOfSquares(N, S);}// This code is contributed by 29AjayKumar |
Java
// Java program to implement// the above approachimport java.io.*;import java.util.*;class GFG { // Function to find the maximum // sum of squares of stack elements public static void maxSumOfSquares( int N, int S) { // Stores the sum ofsquares // of stack elements int res = 0; // Check if sum is valid if (S < N || S > 9 * N) { System.out.println(-1); return; } // Initialize all stack // elements with 1 S = S - N; // Stores the count the // number of stack elements // not equal to 1 int c = 0; // Add the sum of squares of // stack elements not equal to 1 while (S > 0) { c++; if (S / 8 > 0) { res += 9 * 9; S -= 8; } else { res += (S + 1) * (S + 1); break; } } // Add 1 * 1 to res as the // remaining stack elements are 1 res = res + (N - c); // Print the result System.out.println(res); } // Driver Code public static void main(String args[]) { int N = 3; int S = 12; // Function call maxSumOfSquares(N, S); }} |
Python3
# Python3 program to implement# the above approach# Function to find the maximum# sum of squares of stack elementsdef maxSumOfSquares(N, S): # Stores the sum ofsquares # of stack elements res = 0 # Check if sum is valid if (S < N or S > 9 * N): cout << -1; return # Initialize all stack # elements with 1 S = S - N # Stores the count the # number of stack elements # not equal to 1 c = 0 # Add the sum of squares of # stack elements not equal to 1 while (S > 0): c += 1 if (S // 8 > 0): res += 9 * 9 S -= 8 else: res += (S + 1) * (S + 1) break # Add 1 * 1 to res as the # remaining stack elements are 1 res = res + (N - c) # Print the result print(res)# Driver Codeif __name__ == '__main__': N = 3 S = 12 # Function call maxSumOfSquares(N, S)# This code is contributed by mohit kumar 29 |
C#
// C# program to implement// the above approachusing System;class GFG{// Function to find the maximum// sum of squares of stack elementspublic static void maxSumOfSquares(int N, int S){ // Stores the sum ofsquares // of stack elements int res = 0; // Check if sum is valid if (S < N || S > 9 * N) { Console.WriteLine(-1); return; } // Initialize all stack // elements with 1 S = S - N; // Stores the count the // number of stack elements // not equal to 1 int c = 0; // Add the sum of squares of // stack elements not equal to 1 while (S > 0) { c++; if (S / 8 > 0) { res += 9 * 9; S -= 8; } else { res += (S + 1) * (S + 1); break; } } // Add 1 * 1 to res // as the remaining // stack elements are 1 res = res + (N - c); // Print the result Console.WriteLine(res);}// Driver Codepublic static void Main(String []args){ int N = 3; int S = 12; // Function call maxSumOfSquares(N, S);}}// This code is contributed by shikhasingrajput |
Javascript
<script>// javascript program to implement// the above approach // Function to find the maximum // sum of squares of stack elements function maxSumOfSquares(N , S) { // Stores the sum ofsquares // of stack elements var res = 0; // Check if sum is valid if (S < N || S > 9 * N) { document.write(-1); return; } // Initialize all stack // elements with 1 S = S - N; // Stores the count the // number of stack elements // not equal to 1 var c = 0; // Add the sum of squares of // stack elements not equal to 1 while (S > 0) { c++; if (parseInt(S / 8) > 0) { res += 9 * 9; S -= 8; } else { res += (S + 1) * (S + 1); break; } } // Add 1 * 1 to res as the // remaining stack elements are 1 res = res + (N - c); // Print the result document.write(res); } // Driver Code var N = 3; var S = 12; // Function call maxSumOfSquares(N, S);// This code contributed by aashish1995</script> |
Output:
86
Time Complexity: O(N)
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!
