Dados los números enteros N y K , la tarea es construir una array arr[] de tamaño N usando números en el rango [1, N] de modo que tenga K sub-arrays cuyos elementos sean distintos.
Nota: Si hay varias respuestas posibles, devuelva cualquiera de ellas.
Ejemplos:
Entrada: N = 5, K = 8
Salida: {1, 2, 3, 3, 3}
Explicación: Esta array tiene distintas sub-arrays como {1}, {2}, {3}, {3}, { 3}, {1, 2}, {2, 3}, {1, 2, 3}Entrada: N = 6, K = 21
Salida: {1, 2, 3, 4, 5, 6}
Explicación: Esta array tiene 21 sub-arrays distintas.
Planteamiento: La idea para resolver el problema se basa en la siguiente observación matemática:
- N elementos definitivamente formarán N subarreglos de tamaño 1 que tienen elementos únicos.
- Ahora la tarea restante es formar una array tal que (las subarreglas NK) de tamaño superior a 1 tengan todos los elementos distintos.
- También se sabe que el número de subarreglos de tamaño superior a 1 de X elementos son (X*(X+1))/2 – X = X*(X-1)/2 .
- Si los elementos X son distintos, todos estos subarreglos tienen todos los elementos distintos.
Entonces, para formar la array, se necesitan X elementos distintos tales que X*(X-1)/2 = KN.
Entonces, en cada paso, agregue un elemento distinto hasta que se cumpla la condición anterior. Después de eso, repita el último elemento hasta que el tamaño de la array se convierta en N (porque si se repite el último elemento, no afectará el conteo de subarreglos con todos los elementos distintos).
Siga estos pasos para resolver el problema:
- Disminuya K por K – N porque cada número entero contribuye a un subarreglo distinto de tamaño 1.
- Ahora inicialice una variable num = 0 para realizar un seguimiento de los enteros que se agregan a la array y la cantidad de subarreglos formados.
- De K, disminuya el número de subarreglos distintos formados después de agregar (num + 1) al nuevo arreglo. (hasta núm <= K ).
- Compruebe si el tamaño de la array ha llegado a N. Si no, agregue el número: K repetidas veces hasta que se llene la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to construct the array
// with k distinct subarrays
vector<int> construct_array(int n, int k)
{
// Each individual integers
// contributes to one subarray
k = k - n;
// Initialize a variable to keep
// track of integers that are
// adding to to the array
int num = 0;
// Initialize the res to
// store the array
vector<int> res;
// Push as many possible distinct
// integers into the vector
while (k >= num) {
res.push_back(num + 1);
// Decrement the count of
// distinct subarrays incrementing
k -= num;
num++;
}
// If still it is not possible to
// get the array of size n then
// adding n-k at the end make num-k
// more distinct subarrays
while (res.size() < n) {
res.push_back(num - k);
}
// Return the array
return res;
}
// Driver code
int main()
{
int N = 5;
int K = 8;
// Function call
vector<int> ans = construct_array(N, K);
for (int x : ans)
cout << x << " ";
return 0;
}
Java
// JAVA program for the above approach
import java.util.*;
class GFG {
// Function to construct the array
// with k distinct subarrays
public static ArrayList<Integer> construct_array(int n,
int k)
{
// Each individual integers
// contributes to one subarray
k = k - n;
// Initialize a variable to keep
// track of integers that are
// adding to to the array
int num = 0;
// Initialize the res to
// store the array
ArrayList<Integer> res = new ArrayList<Integer>();
// Push as many possible distinct
// integers into the vector
while (k >= num) {
res.add(num + 1);
// Decrement the count of
// distinct subarrays incrementing
k -= num;
num++;
}
// If still it is not possible to
// get the array of size n then
// adding n-k at the end make num-k
// more distinct subarrays
while (res.size() < n) {
res.add(num - k);
}
// Return the array
return res;
}
// Driver code
public static void main(String[] args)
{
int N = 5;
int K = 8;
// Function call
ArrayList<Integer> ans = construct_array(N, K);
for (int x = 0; x < ans.size(); x++)
System.out.print(ans.get(x) + " ");
}
}
// This code is contributed by Taranpreet
Python3
# Python3 code to implement the approach
# Function to construct the array
# with k distinct subarrays
def construct_array(n, k):
# Each individual integers
# contributes to one subarray
k -= n
# // Initialize a variable to keep
# track of integers that are
# adding to to the array
num = 0
# Initialize the res to
# store the array
res = []
# Push as many possible distinct
# integers into the vector
while k >= num:
res.append(num + 1)
# Decrement the count of
# distinct subarrays incrementing
k -= num
num += 1
# If still it is not possible to
# get the array of size n then
# adding n-k at the end make num-k
# more distinct subarrays
while len(res) < n:
res.append(num - k)
return res
# Driver code
N = 5
K = 8
# function call
ans = construct_array(N, K)
print(" ".join(list(map(str, ans))))
# This code is contributed by phasing17
C#
// C# program for the above approach
using System;
using System.Collections;
public class GFG{
// Function to construct the array
// with k distinct subarrays
public static ArrayList construct_array(int n,
int k)
{
// Each individual integers
// contributes to one subarray
k = k - n;
// Initialize a variable to keep
// track of integers that are
// adding to to the array
int num = 0;
// Initialize the res to
// store the array
ArrayList res = new ArrayList();
// Push as many possible distinct
// integers into the vector
while (k >= num) {
res.Add(num + 1);
// Decrement the count of
// distinct subarrays incrementing
k -= num;
num++;
}
// If still it is not possible to
// get the array of size n then
// adding n-k at the end make num-k
// more distinct subarrays
while (res.Count < n) {
res.Add(num - k);
}
// Return the array
return res;
}
// Driver code
static public void Main (){
int N = 5;
int K = 8;
// Function call
ArrayList ans = construct_array(N, K);
foreach(int x in ans)
Console.Write(x + " ");
}
}
// This code is contributed by hrithikgarg03188.
Javascript
<script>
// JavaScript program for the above approach
// Function to construct the array
// with k distinct subarrays
const construct_array = (n, k) => {
// Each individual integers
// contributes to one subarray
k = k - n;
// Initialize a variable to keep
// track of integers that are
// adding to to the array
let num = 0;
// Initialize the res to
// store the array
let res = [];
// Push as many possible distinct
// integers into the vector
while (k >= num) {
res.push(num + 1);
// Decrement the count of
// distinct subarrays incrementing
k -= num;
num++;
}
// If still it is not possible to
// get the array of size n then
// adding n-k at the end make num-k
// more distinct subarrays
while (res.length < n) {
res.push(num - k);
}
// Return the array
return res;
}
// Driver code
let N = 5;
let K = 8;
// Function call
let ans = construct_array(N, K);
for (let x in ans)
document.write(`${ans[x]} `);
// This code is contributed by rakeshsahni
</script>
Producción
1 2 3 3 3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por lokeshpotta20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA