Encuentre n enteros positivos que satisfagan las ecuaciones dadas

Dados tres enteros N , X e Y . La tarea es encontrar N enteros positivos que satisfagan las ecuaciones dadas. 

1. un ₁ ² + un ₂ ² + …. + un _norte ² ≥ X
2. un ₁ + un ₂ + …. + un _norte ≤ Y

Si no es posible tal secuencia de enteros, imprima -1 .

Ejemplos:  

Entrada: N = 3, X = 254, Y = 18 
Salida: 1 1 16 
1 ² + 1 ² + 16 ² = 1 + 1 + 256 = 258 que es ≥ X 
1 + 1 + 16 = 18 que es ≤ Y

Entrada: N = 2, X = 3, Y = 2 
Salida: -1 
No existe tal secuencia. 

Enfoque: es fácil ver que para maximizar la suma de cuadrados, uno debe hacer que todos los números excepto el primero sean iguales a 1 y maximizar el primer número. Teniendo esto en cuenta, solo necesitamos verificar si el valor dado de y es lo suficientemente grande como para satisfacer la restricción de que todos los n números son positivos. Si y no es demasiado pequeño, todo lo que necesitamos es asegurarnos de que X ≤ 1 + 1 + … + (y – (n – 1)) ² .

A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find n positive integers
// that satisfy the given conditions
void 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 code
int main()
{
    int n = 3, x = 254, y = 18;
    findIntegers(n, x, y);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
     
// Function to find n positive integers
// that satisfy the given conditions
static 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 code
public static void main (String[] args)
{
    int n = 3, x = 254, y = 18;
    findIntegers(n, x, y);
}
}
 
// This code is contributed by mits

# Python3 implementation of the approach
 
# Function to find n positive integers
# that satisfy the given conditions
def 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 code
n, x, y = 3, 254, 18
findIntegers(n, x, y)
 
# This code is contributed by mohit kumar

// C# implementation of the approach
using System;
using System.Collections;
 
class GFG
{
     
// Function to find n positive integers
// that satisfy the given conditions
static 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 code
static void Main()
{
    int n = 3, x = 254, y = 18;
    findIntegers(n, x, y);
}
}
 
// This code is contributed by mits

<?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
?>

<script>
 
// JavaScript 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
    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>

1 1 16

Complejidad temporal: O(n)
Espacio auxiliar: O(n)