Encuentre números que comiencen desde 1 con una suma como máximo K excluyendo los números dados

Dada una array arr[] y un entero K , la tarea es encontrar los números que comienzan desde 1 con una suma como máximo K excluyendo los elementos de la array dada .
Ejemplos :

Entrada : arr[] = {4, 6, 8, 12}, K = 14
Salida : {1, 2, 3, 5}
Explicación : La suma máxima posible es 11, con elementos como 1, 2, 3 y 5

Entrada : arr[] = {1, 3, 4}, K = 7
Salida : {2, 5}
Explicación : la suma máxima posible es 7, con elementos como 2 y 5

Enfoque: la tarea se puede resolver creando un hashmap para almacenar los elementos de la array dada. Comience a iterar desde 1 y realice un seguimiento de la suma actual y los elementos excluidos al verificar el mapa hash.
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 find the required elements
void solve(vector<int>& arr, int K)
{
 
    // Store the elements of arr[]
    unordered_map<int, int> occ;
 
    for (int i = 0; i < (int)arr.size(); i++)
        occ[arr[i]]++;
 
    // Store the current sum
    int curSum = 0;
 
    // Start from 1
    int cur = 1;
 
    // Store the answer
    vector<int> ans;
 
    while (curSum + cur <= K) {
 
        // Exclude the current element
        if (occ.find(cur) != occ.end()) {
            cur++;
        }
        else {
            curSum += cur;
 
            // Valid element
            ans.push_back(cur);
            cur++;
        }
    }
 
    for (int i = 0; i < (int)ans.size(); i++)
        cout << ans[i] << " ";
}
 
// Driver Code
int main()
{
    vector<int> arr = { 4, 6, 8, 12 };
    int K = 14;
 
    solve(arr, K);
    return 0;
}

// Java program for the above approach
import java.util.ArrayList;
import java.util.HashMap;
 
class GFG {
 
    // Function to find the required elements
    public static void solve(ArrayList<Integer> arr, int K) {
 
        // Store the elements of arr[]
        HashMap<Integer, Integer> occ = new HashMap<Integer, Integer>();
 
        for (int i = 0; i < arr.size(); i++) {
            if (occ.containsKey(arr.get(i))) {
                occ.put(arr.get(i), occ.get(arr.get(i)) + 1);
            } else {
                occ.put(arr.get(i), 1);
            }
        }
 
        // Store the current sum
        int curSum = 0;
 
        // Start from 1
        int cur = 1;
 
        // Store the answer
        ArrayList<Integer> ans = new ArrayList<Integer>();
 
        while (curSum + cur <= K) {
 
            // Exclude the current element
            if (occ.containsKey(cur)) {
                cur++;
            } else {
                curSum += cur;
 
                // Valid element
                ans.add(cur);
                cur++;
            }
        }
 
        for (int i = 0; i < (int) ans.size(); i++)
            System.out.print(ans.get(i) + " ");
    }
 
    // Driver Code
    public static void main(String args[]) {
        ArrayList<Integer> arr = new ArrayList<Integer>();
        arr.add(4);
        arr.add(6);
        arr.add(8);
        arr.add(12);
        int K = 14;
 
        solve(arr, K);
    }
}
 
// This code is contributed by saurabh_jaiswal.

# Python Program to implement
# the above approach
 
# Function to find the required elements
def solve(arr, K):
 
    # Store the elements of arr[]
    occ = {}
 
    for i in range(len(arr)):
        if (arr[i] in occ):
            occ[arr[i]] += 1
        else:
            occ[arr[i]] = 1
 
 
    # Store the current sum
    curSum = 0
 
    # Start from 1
    cur = 1
 
    # Store the answer
    ans = []
 
    while (curSum + cur <= K) :
 
        # Exclude the current element
        if (cur in occ):
            cur += 1
        else:
            curSum += cur
 
            # Valid element
            ans.append(cur)
            cur += 1
         
    for i in range(len(ans)):
        print(ans[i], end=" ")
 
# Driver Code
arr = [4, 6, 8, 12]
K = 14
 
solve(arr, K)
 
# This code is contributed by Saurabh Jaiswal

// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {
 
    // Function to find the required elements
    public static void solve(List<int> arr, int K) {
 
        // Store the elements of []arr
        Dictionary<int, int> occ = new Dictionary<int, int>();
 
        for (int i = 0; i < arr.Count; i++) {
            if (occ.ContainsKey(arr[i])) {
                occ.Add(arr[i], occ[arr[i]] + 1);
            } else {
                occ.Add(arr[i], 1);
            }
        }
 
        // Store the current sum
        int curSum = 0;
 
        // Start from 1
        int cur = 1;
 
        // Store the answer
        List<int> ans = new List<int>();
 
        while (curSum + cur <= K) {
 
            // Exclude the current element
            if (occ.ContainsKey(cur)) {
                cur++;
            } else {
                curSum += cur;
 
                // Valid element
                ans.Add(cur);
                cur++;
            }
        }
 
        for (int i = 0; i < (int) ans.Count; i++)
            Console.Write(ans[i] + " ");
    }
 
    // Driver Code
    public static void Main(String []args) {
        List<int> arr = new List<int>();
        arr.Add(4);
        arr.Add(6);
        arr.Add(8);
        arr.Add(12);
        int K = 14;
 
        solve(arr, K);
    }
}
 
// This code is contributed by shikhasingrajput

<script>
 
      // JavaScript Program to implement
      // the above approach
 
      // Function to find the required elements
      function solve(arr, K) {
 
          // Store the elements of arr[]
          let occ = new Map();
 
          for (let i = 0; i < arr.length; i++) {
              if (occ.has(arr[i])) {
                  occ.set(arr[i], occ.get(arr[i]) + 1)
              }
              else {
                  occ.set(arr[i], 1);
              }
          }
 
 
          // Store the current sum
          let curSum = 0;
 
          // Start from 1
          let cur = 1;
 
          // Store the answer
          let ans = [];
 
          while (curSum + cur <= K) {
 
              // Exclude the current element
              if (occ.has(cur)) {
                  cur++;
              }
              else {
                  curSum += cur;
 
                  // Valid element
                  ans.push(cur);
                  cur++;
              }
          }
 
          for (let i = 0; i < ans.length; i++)
              document.write(ans[i] + " ");
      }
 
      // Driver Code
      let arr = [4, 6, 8, 12];
      let K = 14;
 
      solve(arr, K);
 
  // This code is contributed by Potta Lokesh
  </script>

1 2 3 5 

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