Find numbers starting from 1 with sum at-most K excluding given numbers
Given an array arr[] and an integer K, the task is to find the numbers starting from 1 with sum at-most K excluding elements of the given array
Examples:
Input: arr[] = {4, 6, 8, 12}, K = 14
Output: {1, 2, 3, 5}
Explanation: Maximum possible sum is 11, with elements as 1, 2, 3 and 5Input: arr[] = {1, 3, 4}, K = 7
Output: {2, 5}
Explanation: Maximum possible sum is 7, with elements as 2 and 5
Approach: The task can be solved by creating a hashmap to store the elements of the given array. Start iterating from 1, and keep track of the current sum and the excluded elements by checking the hashmap.
Below is the implementation of the above approach:
C++
// 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
// 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. |
Python3
# 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#
// 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 |
Javascript
<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> |
Output
1 2 3 5
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us