Given three integers N, X, and Y. The task is to find N positive integers that satisfy the given equations.
- a12 + a22 + …. + an2 ? X
- a1 + a2 + …. + an ? Y
If no such sequence of integers is possible then print -1.
Examples:
Input: N = 3, X = 254, Y = 18
Output: 1 1 16
12 + 12 + 162 = 1 + 1 + 256 = 258 which is ? X
1 + 1 + 16 = 18 which is ? YInput: N = 2, X = 3, Y = 2
Output: -1
No such sequence exists.
Approach: It is easy to see that in order to maximize the sum of squares, one should make all numbers except the first one equal to 1 and maximize the first number. Keeping this in mind we only need to check whether the given value of y is large enough to satisfy a restriction that all n numbers are positive. If y is not too small, then all we need is to ensure that X ? 1 + 1 + … + (y – (n – 1))2.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to find n positive integers// that satisfy the given conditionsvoid findIntegers(int n, int x, int y){ // To store n positive integers vector<int> ans; // Place N - 1 one's for (int i = 0; i < n - 1; i++) ans.push_back(1); // If can not place (y - (n - 1)) // as the Nth integer if (y - (n - 1) <= 0) { cout << "-1"; return; } // Place Nth integer ans.push_back(y - (n - 1)); // To store the sum of // squares of N integers int store = 0; for (int i = 0; i < n; i++) store += ans[i] * ans[i]; // If it is less than x if (store < x) { cout << "-1"; return; } // Print the required integers for (int i = 0; i < n; i++) cout << ans[i] << " ";}// Driver codeint main(){ int n = 3, x = 254, y = 18; findIntegers(n, x, y); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{ // Function to find n positive integers// that satisfy the given conditionsstatic void findIntegers(int n, int x, int y){ // To store n positive integers ArrayList<Integer> ans = new ArrayList<Integer>(); // Place N - 1 one's for (int i = 0; i < n - 1; i++) ans.add(1); // If can not place (y - (n - 1)) // as the Nth integer if (y - (n - 1) <= 0) { System.out.print("-1"); return; } // Place Nth integer ans.add(y - (n - 1)); // To store the sum of // squares of N integers int store = 0; for (int i = 0; i < n; i++) store += ans.get(i) * ans.get(i); // If it is less than x if (store < x) { System.out.print("-1"); return; } // Print the required integers for (int i = 0; i < n; i++) System.out.print(ans.get(i)+" ");}// Driver codepublic static void main (String[] args) { int n = 3, x = 254, y = 18; findIntegers(n, x, y);}}// This code is contributed by mits |
Python3
# Python3 implementation of the approach# Function to find n positive integers# that satisfy the given conditionsdef findIntegers(n, x, y): # To store n positive integers ans = [] # Place N - 1 one's for i in range(n - 1): ans.append(1) # If can not place (y - (n - 1)) # as the Nth integer if (y - (n - 1) <= 0): print("-1", end = "") return # Place Nth integer ans.append(y - (n - 1)) # To store the sum of # squares of N integers store = 0 for i in range(n): store += ans[i] * ans[i] # If it is less than x if (store < x): print("-1", end = "") return; # Print the required integers for i in range(n): print(ans[i], end = " ")# Driver coden, x, y = 3, 254, 18findIntegers(n, x, y)# This code is contributed by mohit kumar |
C#
// C# implementation of the approachusing System;using System.Collections;class GFG{ // Function to find n positive integers// that satisfy the given conditionsstatic void findIntegers(int n, int x, int y){ // To store n positive integers ArrayList ans = new ArrayList(); // Place N - 1 one's for (int i = 0; i < n - 1; i++) ans.Add(1); // If can not place (y - (n - 1)) // as the Nth integer if (y - (n - 1) <= 0) { Console.Write("-1"); return; } // Place Nth integer ans.Add(y - (n - 1)); // To store the sum of // squares of N integers int store = 0; for (int i = 0; i < n; i++) store += (int)ans[i] *(int)ans[i]; // If it is less than x if (store < x) { Console.Write("-1"); return; } // Print the required integers for (int i = 0; i < n; i++) Console.Write((int)ans[i]+" ");}// Driver codestatic void Main() { int n = 3, x = 254, y = 18; findIntegers(n, x, y);}}// This code is contributed by mits |
PHP
<?php// Php implementation of the approach // Function to find n positive integers // that satisfy the given conditions function findIntegers($n, $x, $y) { // To store n positive integers $ans = array(); // Place N - 1 one's for ($i = 0; $i < $n - 1; $i++) array_push($ans,1) ; // If can not place (y - (n - 1)) // as the Nth integer if ($y - ($n - 1) <= 0) { echo "-1"; return; } // Place Nth integer array_push($ans,$y - ($n - 1)); // To store the sum of // squares of N integers $store = 0; for ($i = 0; $i < $n; $i++) $store += $ans[$i] * $ans[$i]; // If it is less than x if ($store < $x) { echo "-1"; return; } // Print the required integers for ($i = 0; $i < $n; $i++) echo $ans[$i]," "; } // Driver code $n = 3; $x = 254; $y = 18; findIntegers($n, $x, $y); // This code is contributed by Ryuga?> |
Javascript
<script>// JavaScript implementation of the approach// Function to find n positive integers// that satisfy the given conditionsfunction findIntegers(n, x, y){ // To store n positive integers let ans = []; // Place N - 1 one's for (let i = 0; i < n - 1; i++) ans.push(1); // If can not place (y - (n - 1)) // as the Nth integer if (y - (n - 1) <= 0) { document.write("-1"); return; } // Place Nth integer ans.push(y - (n - 1)); // To store the sum of // squares of N integers let store = 0; for (let i = 0; i < n; i++) store += ans[i] * ans[i]; // If it is less than x if (store < x) { document.write("-1"); return; } // Print the required integers for (let i = 0; i < n; i++) document.write(ans[(i)]+" ");} // Driver Code let n = 3, x = 254, y = 18; findIntegers(n, x, y); </script> |
Output:
1 1 16
Time Complexity: O(n)
Auxiliary Space: O(n)
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!
