Dada una array arr[] de tamaño N y un número K , la tarea es encontrar la suma de los primeros K números naturales que no están presentes en la array dada.
Ejemplos:
Entrada: arr[] = {2, 3, 4}, K = 3
Salida: 12
Explicación: Los primeros 3 números que faltan son: [1, 5, 6]Entrada: arr[] = {-2, -3, 4}, K = 2
Salida: 3
Explicación: Los números que faltan son: [1 2]
Planteamiento: El problema se puede resolver a partir de la siguiente idea:
Almacene los números positivos en el conjunto y calcule las sumas de los números presentes entre dos números del conjunto utilizando la fórmula para la suma de todos los números de L a R (digamos X) = (R-1)*R/2 – (L+ 1)*L/2.
Verifique todos los intervalos entre dos números y calcule su suma hasta que no se consideren K elementos.
Siga los pasos que se mencionan a continuación para resolver el problema:
- Cree un conjunto ordenado a partir de elementos de array para eliminar todos los duplicados.
- Luego, para cada número positivo desde el comienzo del conjunto:
- Encuentra el conteo de números entre 2 números positivos en el conjunto
- Si el conteo es más pequeño que K , encuentre la suma de los números entre esos 2 números en el conjunto y reduzca K por conteo
- Si el conteo es mayor que K , encuentre la suma de solo K números del número positivo anterior y reduzca K a 0
- devolver la suma
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 find the sum between 0 to n
long long sumN(long long n)
{
return n * (n + 1) / 2;
}
// Function to calculate the subsequence sum
long long printKMissingSum(vector<int>& nums,
int k)
{
set<int> s(nums.begin(), nums.end());
int a, b, prev, cnt;
// Create one variable ans
long long ans = 0;
// Loop to calculate the sum
for (auto itr = s.begin();
itr != s.end() && k > 0; itr++) {
b = *itr;
if (b < 0) {
a = 0;
prev = 0;
continue;
}
a = (itr == s.begin() ? 0 : prev);
cnt = b - 1 - a;
if (cnt <= k) {
ans += sumN(b - 1) - sumN(a);
k -= cnt;
}
else {
ans += sumN(a + k) - sumN(a);
k -= k;
}
prev = b;
}
if (k > 0) {
ans += sumN(prev + k) - sumN(prev);
k -= k;
}
return ans;
}
// Driver code
int main()
{
vector<int> arr = { -2, -3, -4 };
int K = 2;
cout << printKMissingSum(arr, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find the sum between 0 to n
public static long sumN(long n)
{
return n * (n + 1) / 2;
}
// Function to calculate the subsequence sum
public static long printKMissingSum(int nums[], int k)
{
HashSet<Integer> s = new HashSet<Integer>();
for (int i : nums)
s.add(i);
int a = 0, b = 0, prev = 0, cnt = 0;
// Create one variable ans
long ans = 0;
// Loop to calculate the sum
Iterator<Integer> it = s.iterator();
int tempk = k;
while (it.hasNext() && k > 0) {
b = it.next();
if (b < 0) {
a = 0;
prev = 0;
continue;
}
a = (k == tempk ? 0 : prev);
cnt = b - 1 - a;
if (cnt <= k) {
ans += sumN(b - 1) - sumN(a);
k -= cnt;
}
else {
ans += sumN(a + k) - sumN(a);
k -= k;
}
prev = b;
}
if (k > 0) {
ans += sumN(prev + k) - sumN(prev);
k -= k;
}
return ans;
}
public static void main(String[] args)
{
int arr[] = { -2, -3, -4 };
int K = 2;
System.out.print(printKMissingSum(arr, K));
}
}
// This code is contributed by Rohit Pradhan
Python3
# Python program for the above approach # Function to find the sum between 0 to n def sumN(n): return (n * (n + 1)) / 2 # Function to calculate the subsequence sum def printKMissingSum(nums, k): s = set(nums) s = list(s) ans = 0 itr = 0 while itr < len(s) and k > 0: b = s[itr] if b < 0: a = 0 prev = 0 break a = 0 if itr == 0 else prev cnt = b - 1 - a if cnt <= k: ans += sumN(b - 1) - sumN(a) k -= cnt else: ans += sumN(a + k) - sumN(a) k -= k prev = b itr += 1 if k > 0: ans += sumN(prev + k) - sumN(a) k -= k return int(ans) # Driver code nums = [-2, -3, -4] k = 2 print(printKMissingSum(nums, k)) # This code is contributed by amnindersingh1414.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG{
// Function to find the sum between 0 to n
static long sumN(long n)
{
return n * (n + 1) / 2;
}
// Function to calculate the subsequence sum
static long printKMissingSum(int[] nums, int k)
{
HashSet<int> s = new HashSet<int>();
foreach (var i in nums)
s.Add(i);
int a = 0, b = 0, prev = 0, cnt = 0;
// Create one variable ans
long ans = 0;
// Loop to calculate the sum
HashSet<int>.Enumerator it = s.GetEnumerator();
int tempk = k;
while (it.MoveNext() && k > 0) {
b = it.Current;
if (b < 0) {
a = 0;
prev = 0;
continue;
}
a = (k == tempk ? 0 : prev);
cnt = b - 1 - a;
if (cnt <= k) {
ans += sumN(b - 1) - sumN(a);
k -= cnt;
}
else {
ans += sumN(a + k) - sumN(a);
k -= k;
}
prev = b;
}
if (k > 0) {
ans += sumN(prev + k) - sumN(prev);
k -= k;
}
return ans;
}
static public void Main ()
{
int[] arr = { -2, -3, -4 };
int K = 2;
Console.Write(printKMissingSum(arr, K));
}
}
// This code is contributed by hrithikgarg03188.
Javascript
<script>
// JavaScript program for the above approach
// Function to find the sum between 0 to n
const sumN = (n) => {
return n * (n + 1) / 2;
}
// Function to calculate the subsequence sum
const printKMissingSum = (nums, k) => {
let s = new Set();
for (let itm in nums) s.add(nums[itm]);
s = Array.from(s);
let a, b, prev, cnt;
// Create one variable ans
let ans = 0;
// Loop to calculate the sum
for (let itr = 0; itr < s.length && k > 0; itr++) {
b = s[itr];
if (b < 0) {
a = 0;
prev = 0;
continue;
}
a = (itr == 0 ? 0 : prev);
cnt = b - 1 - a;
if (cnt <= k) {
ans += sumN(b - 1) - sumN(a);
k -= cnt;
}
else {
ans += sumN(a + k) - sumN(a);
k -= k;
}
prev = b;
}
if (k > 0) {
ans += sumN(prev + k) - sumN(prev);
k -= k;
}
return ans;
}
// Driver code
let arr = [-2, -3, -4];
let K = 2;
document.write(printKMissingSum(arr, K));
// This code is contributed by rakeshsahni
</script>
Producción
3
Complejidad de tiempo : O(N * logN)
Espacio auxiliar : O(N)