Número máximo posible en una Secuencia de elementos distintos con Promedio dado

Dados los números enteros N y K , la tarea es encontrar el número máximo posible que puede tener una secuencia de longitud N de enteros positivos distintos si el promedio de los elementos de la secuencia es K .

Ejemplos:

Entrada : N = 4, K = 3
Salida : 6
Explicación : La secuencia deseada sería – {1, 2, 3, 6}. 
Podría haber otras secuencias que también satisfagan los valores dados de N y K, como {1, 2, 4, 5}.
Pero, dado que se necesita el máximo número posible en la secuencia, 6 sería la respuesta.

Entrada : N = 5, K = 4
Salida : 10
Explicación : La secuencia deseada sería – {1, 2, 3, 4, 10}.

Entrada: N = 5, K = 2
Salida: -1
Explicación: No es posible formar una secuencia que tenga 5 enteros positivos distintos y un promedio de 2.

Planteamiento: La solución al problema se basa en la siguiente observación:

• A partir del número de enteros en la secuencia y el promedio de la secuencia, la suma total de todos los números de la secuencia se puede calcular fácilmente mediante la siguiente fórmula: 
  suma de todos los números en secuencia = (número de términos) x (promedio de todos los términos)
• Ahora, suponga que el término máximo (o número) es M y la suma de la secuencia es S. Entonces, para maximizar M , (SM) debe minimizarse.
• Como , los términos deben ser distintos y positivos, por lo que la serie con mínima suma posible sería 1, 2, 3 . . . (N-1) .
  La suma de tal secuencia de números naturales se puede calcular fácilmente para (N-1) términos, y sería: (N * (N – 1)) / 2 .
• Entonces, el entero máximo posible sería: M = suma de la secuencia dada – suma de los primeros (N-1) números naturales .

Siga los pasos que se mencionan a continuación:

• Calcula la suma de la sucesión dada.
• Encuentra la suma de los primeros (N-1) números naturales.
• Calcula el número máximo posible a partir de la observación anterior.
• Si el valor máximo es menor que N, entonces no es posible tal secuencia.
• De lo contrario, el valor máximo es la respuesta requerida.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the
// maximum possible number in a sequence
// with given average and number of terms.
int maxNumber(int N, int K)
{
    // Sum of the sequence
    int sum = N * K;
 
    // Minimum possible sum of a sequence
    // having N-1 distinct positive integers
    int minSum = N * (N - 1) / 2;
 
    // Maximum number of the given sequence
    int maxNum = sum - minSum;
 
    // If such sequence is not possible
    if (maxNum < N)
        return -1;
   
    return maxNum;
}
 
// Driver Code
int main()
{
    int N = 5, K = 4;
    int maximum_number = maxNumber(N, K);
    cout << maximum_number;
    return 0;
}

// Java program for the above approach
import java.util.*;
public class GFG
{
     
// Function to calculate the
// maximum possible number in a sequence
// with given average and number of terms.
static int maxNumber(int N, int K)
{
   
    // Sum of the sequence
    int sum = N * K;
 
    // Minimum possible sum of a sequence
    // having N-1 distinct positive integers
    int minSum = N * (N - 1) / 2;
 
    // Maximum number of the given sequence
    int maxNum = sum - minSum;
 
    // If such sequence is not possible
    if (maxNum < N)
        return -1;
   
    return maxNum;
}
 
// Driver Code
public static void main(String args[])
{
    int N = 5, K = 4;
    int maximum_number = maxNumber(N, K);
    System.out.println(maximum_number);
}
}
 
// This code is contributed by Samim Hossain Mondal.

# Python code for the above approach
# Function to calculate the
# maximum possible number in a sequence
# with given average and number of terms.
def maxNumber(N, K):
 
    # Sum of the sequence
    sum = N * K;
 
    # Minimum possible sum of a sequence
    # having N-1 distinct positive integers
    minSum = (N * (N - 1) // 2);
 
    # Maximum number of the given sequence
    maxNum = sum - minSum;
 
    # If such sequence is not possible
    if (maxNum < N):
        return -1;
 
    return maxNum;
 
# Driver Code
N = 5
K = 4;
maximum_number = maxNumber(N, K);
print(maximum_number);
 
# This code is contributed by gfgking

using System;
 
public class GFG{
 
  // Function to calculate the
  // maximum possible number in a sequence
  // with given average and number of terms.
  static int maxNumber(int N, int K)
  {
    // Sum of the sequence
    int sum = N * K;
 
    // Minimum possible sum of a sequence
    // having N-1 distinct positive integers
    int minSum = N * (N - 1) / 2;
 
    // Maximum number of the given sequence
    int maxNum = sum - minSum;
 
    // If such sequence is not possible
    if (maxNum < N)
      return -1;
 
    return maxNum;
  }
 
  // Driver Code
  static public void Main (){
 
    int N = 5, K = 4;
    int maximum_number = maxNumber(N, K);
    Console.Write(maximum_number);
  }
}
 
// This code is contributed by hrithikgarg03188

<script>
       // JavaScript code for the above approach
       // Function to calculate the
       // maximum possible number in a sequence
       // with given average and number of terms.
       function maxNumber(N, K)
       {
        
           // Sum of the sequence
           let sum = N * K;
 
           // Minimum possible sum of a sequence
           // having N-1 distinct positive integers
           let minSum = Math.floor(N * (N - 1) / 2);
 
           // Maximum number of the given sequence
           let maxNum = sum - minSum;
 
           // If such sequence is not possible
           if (maxNum < N)
               return -1;
 
           return maxNum;
       }
 
       // Driver Code
       let N = 5, K = 4;
       let maximum_number = maxNumber(N, K);
       document.write(maximum_number);
 
      // This code is contributed by Potta Lokesh
   </script>

10

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)