Count of distinct integers in range [1, N] that do not have any subset sum as K
Given two positive integers N and K such that K?N, the task is to find the maximum number of distinct integers in the range [1, N] having no subset with a sum equal to K. If there are multiple solutions, print any.
Examples:
Input: N = 5, K = 3
Output: 1 4 5
Explanation: There are two sets of distinct numbers of size 3 which don’t have any subset sum of 3.
These are {1, 4, 5} and {2, 4, 5}. So, print any of them in any order.Input: N = 1, K =1
Output: 0
Approach: The idea is based on the following observations:
- Any number greater than K can be chosen as they can never contribute to a subset whose sum is K.
- K cannot be chosen.
- For the numbers less than K, at most K/2 numbers can be chosen. For example:
- If K=5, 1+4=5, and 2+3=5, so either 1 can be chosen or 4 and similarly either 2 or 3 can be chosen. Thus, at most (5/2=2) numbers can be chosen.
- If K=6, 1+5=6, 2+4=6 and 3+3=6. Again, 3 numbers can be chosen such that no subset-sum equals 6. 3 can always be chosen as only distinct numbers are being chosen, and either 1 or 5 and similarly either 2 or 4 can be chosen. Thus, at most (6/3=3) numbers can be chosen.
- Therefore, the maximum number of distinct numbers that can be chosen is (N-K)+(K/2).
Follow the below steps to solve the problem:
- The maximum number of distinct digits that can be chosen is (N-K)+(K/2).
- All the numbers greater than K need to be chosen i.e N-K numbers from the end. K/2 elements less than K also need to be chosen.
- Thus, a possible solution is to choose (N-K)+(K/2) consecutive numbers starting from N and excluding K.
- The easiest way to do this is to create an array storing all values from 1 to N, except for K, reverse the array, and print (N-K)+(K/2) elements from the beginning.
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 maximum number of distinct integers // in [1, N] having no subset with sum equal to K void findSet( int N, int K) { // Declare a vector to store // the required numbers vector< int > a; // Store all the numbers in [1, N] except K for ( int i = 1; i <= N; i++) { if (i != K) a.push_back(i); } // Store the maximum number // of distinct numbers int MaxDistinct = (N - K) + (K / 2); // Reverse the array reverse(a.begin(), a.end()); // Print the required numbers for ( int i = 0; i < MaxDistinct; i++) cout << a[i] << " " ; } // Driver Code int main() { // Given Input int N = 5, K = 3; // Function Call findSet(N, K); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find maximum number of distinct // integers in [1, N] having no subset with // sum equal to K static void findSet( int N, int K) { // Declare a vector to store // the required numbers ArrayList<Integer> a = new ArrayList<Integer>(); // Store all the numbers in [1, N] except K for ( int i = 1 ; i <= N; i++) { if (i != K) a.add(i); } // Store the maximum number // of distinct numbers int MaxDistinct = (N - K) + (K / 2 ); // Reverse the array Collections.reverse(a); // Print the required numbers for ( int i = 0 ; i < MaxDistinct; i++) System.out.print(a.get(i) + " " ); } // Driver Code public static void main(String[] args) { // Given Input int N = 5 , K = 3 ; // Function Call findSet(N, K); } } // This code is contributed by sanjoy_62 |
Python3
# Python3 program for the above approach # Function to find maximum number of distinct # integers in [1, N] having no subset with # sum equal to K def findSet(N, K): # Declare a vector to store # the required numbers a = [] # Store all the numbers in [1, N] except K for i in range ( 1 , N + 1 ): if (i ! = K): a.append(i) # Store the maximum number # of distinct numbers MaxDistinct = (N - K) + (K / / 2 ) # Reverse the array a = a[:: - 1 ] # Print the required numbers for i in range (MaxDistinct): print (a[i], end = " " ) # Driver Code if __name__ = = '__main__' : # Given Input N = 5 K = 3 # Function Call findSet(N, K) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to find maximum number of distinct // integers in [1, N] having no subset with // sum equal to K static void findSet( int N, int K) { // Declare a vector to store // the required numbers List< int > a = new List< int >(); // Store all the numbers in [1, N] except K for ( int i = 1; i <= N; i++) { if (i != K) a.Add(i); } // Store the maximum number // of distinct numbers int MaxDistinct = (N - K) + (K / 2); // Reverse the array a.Reverse(); // Print the required numbers for ( int i = 0; i < MaxDistinct; i++) Console.Write(a[i] + " " ); } // Driver Code public static void Main() { // Given Input int N = 5, K = 3; // Function Call findSet(N, K); } } // This code is contributed by avijitmondal1998. |
Javascript
<script> // JavaScript program for the above approach // Function to find maximum number of distinct integers // in [1, N] having no subset with sum equal to K function findSet( N, K) { // Declare a vector to store // the required numbers let a = []; // Store all the numbers in [1, N] except K for (let i = 1; i <= N; i++) { if (i != K) a.push(i); } // Store the maximum number // of distinct numbers let MaxDistinct = (N - K) + parseInt(K / 2); // Reverse the array a.reverse(); // Print the required numbers for (let i = 0; i < MaxDistinct; i++) document.write(a[i]+ " " ); } // Driver Code // Given Input let N = 5, K = 3; // Function Call findSet(N, K); // This code is contributed by Potta Lokesh </script> |
Output
5 4 2
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us