Dados dos enteros N y K , la tarea es generar una array arr[] de longitud K tal que:
- arr[0] + arr[1] + … + arr[K – 1] = norte .
- arr[i] > 0 para 0 ≤ yo < K .
- arr[i] < arr[i + 1] ≤ 2 * arr[i] para 0 ≤ yo < K – 1 .
Si hay varias respuestas, encuentre cualquiera de ellas; de lo contrario, imprima -1 .
Ejemplos:
Entrada: N = 26, K = 6
Salida: 1 2 4 5 6 8
La array generada satisface todas las condiciones dadas.
Entrada: N = 8, K = 3
Salida: -1
Enfoque: Sea r = n – k * (k + 1) / 2 . Si r < 0 , la respuesta ya es -1 . De lo contrario, construyamos el arreglo arr[] , donde todos los arr[i] son floor(r / k) excepto los valores de r % k más a la derecha , que son ceil(r / k) .
Es fácil ver que la suma de esta array es r , está ordenada en orden no decreciente y la diferencia entre el elemento máximo y mínimo no es mayor que 1.
Agreguemos 1 a arr[1] , 2 a arr [2], y así sucesivamente (esto es lo que restamos de n al principio).
Entonces, si r != k – 1 o k = 1 entonces arr[] es nuestra array requerida. De lo contrario, obtuvimos una array de tipo 1, 3, ….., arr[k] . Para k = 2 o k = 3 , no hay respuesta para este caso. De lo contrario, podemos restar 1 de arr[2] y sumarlo a arr[k] y esta respuesta será correcta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to generate and print
// the required array
void generateArray(int n, int k)
{
// Initializing the array
vector<int> array(k, 0);
// Finding r (from above approach)
int remaining = n - int(k * (k + 1) / 2);
// If r<0
if (remaining < 0)
cout << ("NO");
int right_most = remaining % k;
// Finding ceiling and floor values
int high = ceil(remaining / (k * 1.0));
int low = floor(remaining / (k * 1.0));
// Fill the array with ceiling values
for (int i = k - right_most; i < k; i++)
array[i]= high;
// Fill the array with floor values
for (int i = 0; i < (k - right_most); i++)
array[i]= low;
// Add 1, 2, 3, ... with corresponding values
for (int i = 0; i < k; i++)
array[i] += i + 1;
if (k - 1 != remaining or k == 1)
{
for(int u:array) cout << u << " ";
}
// There is no solution for below cases
else if (k == 2 or k == 3)
printf("-1\n");
else
{
// Modify A[1] and A[k-1] to get
// the required array
array[1] -= 1;
array[k - 1] += 1;
for(int u:array) cout << u << " ";
}
}
// Driver Code
int main()
{
int n = 26, k = 6;
generateArray(n, k);
return 0;
}
// This code is contributed
// by Mohit Kumar
Java
// Java implementation of the approach
class GFG
{
// Function to generate and print
// the required array
static void generateArray(int n, int k)
{
// Initializing the array
int []array = new int[k];
// Finding r (from above approach)
int remaining = n - (k * (k + 1) / 2);
// If r < 0
if (remaining < 0)
System.out.print("NO");
int right_most = remaining % k;
// Finding ceiling and floor values
int high = (int) Math.ceil(remaining / (k * 1.0));
int low = (int) Math.floor(remaining / (k * 1.0));
// Fill the array with ceiling values
for (int i = k - right_most; i < k; i++)
array[i] = high;
// Fill the array with floor values
for (int i = 0; i < (k - right_most); i++)
array[i] = low;
// Add 1, 2, 3, ... with corresponding values
for (int i = 0; i < k; i++)
array[i] += i + 1;
if (k - 1 != remaining || k == 1)
{
for(int u:array)
System.out.print(u + " ");
}
// There is no solution for below cases
else if (k == 2 || k == 3)
System.out.printf("-1\n");
else
{
// Modify A[1] and A[k-1] to get
// the required array
array[1] -= 1;
array[k - 1] += 1;
for(int u:array)
System.out.print(u + " ");
}
}
// Driver Code
public static void main(String[] args)
{
int n = 26, k = 6;
generateArray(n, k);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation of the approach
import sys
from math import floor, ceil
# Function to generate and print
# the required array
def generateArray(n, k):
# Initializing the array
array = [0] * k
# Finding r (from above approach)
remaining = n-int(k*(k + 1)/2)
# If r<0
if remaining<0:
print("NO")
sys.exit()
right_most = remaining % k
# Finding ceiling and floor values
high = ceil(remaining / k)
low = floor(remaining / k)
# Fill the array with ceiling values
for i in range(k-right_most, k):
array[i]= high
# Fill the array with floor values
for i in range(k-right_most):
array[i]= low
# Add 1, 2, 3, ... with corresponding values
for i in range(k):
array[i]+= i + 1
if k-1 != remaining or k == 1:
print(*array)
sys.exit()
# There is no solution for below cases
elif k == 2 or k == 3:
print("-1")
sys.exit()
else:
# Modify A[1] and A[k-1] to get
# the required array
array[1]-= 1
array[k-1]+= 1
print(*array)
sys.exit()
# Driver Code
if __name__=="__main__":
n, k = 26, 6
generateArray(n, k)
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to generate and print
// the required array
static void generateArray(int n, int k)
{
// Initializing the array
int []array = new int[k];
// Finding r (from above approach)
int remaining = n - (k * (k + 1) / 2);
// If r < 0
if (remaining < 0)
Console.Write("NO");
int right_most = remaining % k;
// Finding ceiling and floor values
int high = (int) Math.Ceiling(remaining /
(k * 1.0));
int low = (int) Math.Floor(remaining /
(k * 1.0));
// Fill the array with ceiling values
for (int i = k - right_most; i < k; i++)
array[i] = high;
// Fill the array with floor values
for (int i = 0;
i < (k - right_most); i++)
array[i] = low;
// Add 1, 2, 3, ... with
// corresponding values
for (int i = 0; i < k; i++)
array[i] += i + 1;
if (k - 1 != remaining || k == 1)
{
foreach(int u in array)
Console.Write(u + " ");
}
// There is no solution for below cases
else if (k == 2 || k == 3)
Console.Write("-1\n");
else
{
// Modify A[1] and A[k-1] to get
// the required array
array[1] -= 1;
array[k - 1] += 1;
foreach(int u in array)
Console.Write(u + " ");
}
}
// Driver Code
public static void Main(String[] args)
{
int n = 26, k = 6;
generateArray(n, k);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// javascript implementation of the approach
// Function to generate and print
// the required array
function generateArray(n , k) {
// Initializing the array
var array = Array(k).fill(0);
// Finding r (from above approach)
var remaining = n - parseInt(k * (k + 1) / 2);
// If r < 0
if (remaining < 0)
document.write("NO");
var right_most = remaining % k;
// Finding ceiling and floor values
var high = parseInt( Math.ceil(remaining / (k * 1.0)));
var low = parseInt( Math.floor(remaining / (k * 1.0)));
// Fill the array with ceiling values
for (i = k - right_most; i < k; i++)
array[i] = high;
// Fill the array with floor values
for (i = 0; i < (k - right_most); i++)
array[i] = low;
// Add 1, 2, 3, ... with corresponding values
for (i = 0; i < k; i++)
array[i] += i + 1;
if (k - 1 != remaining || k == 1) {
for (var u = 0;u< array.length;u++)
document.write(array[u] + " ");
}
// There is no solution for below cases
else if (k == 2 || k == 3)
document.write("-1");
else {
// Modify A[1] and A[k-1] to get
// the required array
array[1] -= 1;
array[k - 1] += 1;
for (var f = 0;f< array.length;f++)
document.write(array[f] + " ");
}
}
// Driver Code
var n = 26, k = 6;
generateArray(n, k);
// This code is contributed by todaysgaurav
</script>
Producción:
1 2 4 5 6 8
Complejidad de tiempo: O(K)
Espacio Auxiliar: O(K)
Publicación traducida automáticamente
Artículo escrito por saurabh sisodia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA