Given two integers N and K, the task is to find the Nth Subset from the sequence of subsets generated from the powers of K i.e. {1, K1, K2, K3, …..} such that the subsets are arranged in increasing order of their sum, the task is to find the Nth subset from the sequence.
Examples:
Input: N = 5, K = 3
Output: 1 9
Explanation:
The sequence of subsets along with their sum are:
- Subset = {1}, Sum = 1
- Subset = {3}, Sum = 3
- Subset = {1, 3}, Sum = 4
- Subset = {9}, Sum = 9
- Subset = {1, 9}, Sum = 10
Therefore, the subset at position 5 is {1, 9}.
Input: N = 4, K = 4
Output: 16
Approach:
Let’s refer to the required sequence for K = 3 given below:
From the above sequence, it can be observed that the subset {3} has position 2, the subset {9} has position 4, and the subset {27} has position 8, and so on. The subset {1, 3}, {1, 9}, {1, 27} occupies positions 3, 5, and 9 respectively. Hence, all the elements of the required Nth subset can be obtained by finding the nearest power of 2 which is smaller than or equal to N.
Illustration:
N = 6, K = 3
1st iteration:
- p = log2(6) = 2
- 32 = 9, Subset = {9}
- N = 6 % 4 = 2
2nd iteration:
- p = log2(2) = 1
- 31 = 3, Subset = {3, 9}
- N = 2 % 2 = 0
Therefore, the required subset is {3, 9}
Follow the steps below to solve the problem:
- Calculate the nearest power of 2 which is smaller than or equal to N, say p. Therefore, p = log2N.
- Now, the element of the subset will be Kp. Insert it into the front of the subset.
- Update N to N % 2p.
- Repeat the above steps until N becomes 0, and consequently print the obtained subset.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h>#include <stdio.h>using namespace std;#define lli long long int// Function to print the // required N-th subset void printSubset(lli n, int k){ vector<lli> answer; while(n > 0) { // Nearest power of 2<=N lli p = log2(n); // Now insert k^p in the answer answer.push_back(pow(k, p)); // update n n %= (int)pow(2, p); } // Print the ans in sorted order reverse(answer.begin(), answer.end()); for(auto x: answer) { cout << x << " "; }}// Driver Codeint main(){ lli n = 5; int k = 4; printSubset(n, k);}// This code is contributed by winter_soldier |
Java
// Java program for above approachimport java.util.*;import java.lang.*;import java.io.*;class GFG{ // Function to print the // required N-th subset static void printSubset(long n, int k) { ArrayList<Long> answer = new ArrayList<>(); while(n > 0) { // Nearest power of 2<=N long p = (long)(Math.log(n) / Math.log(2));; // Now insert k^p in the answer answer.add((long)(Math.pow(k, p))); // update n n %= (int)Math.pow(2, p); } // Print the ans in sorted order Collections.sort(answer); for(Long x: answer) { System.out.print(x + " "); } } // Driver function public static void main (String[] args) { long n = 5; int k = 4; printSubset(n, k); }}// This code is contributed by offbeat |
Python3
# Python3 program for# the above approachimport math# Function to print the# required N-th subsetdef printSubset(N, K): # Stores the subset answer = "" while(N > 0): # Nearest power of 2 <= N p = int(math.log(N, 2)) # Insert K ^ p in the subset answer = str(K**p)+" "+answer # Update N N = N % (2**p) # Print the subset print(answer) # Driver CodeN = 5K = 4printSubset(N, K) |
C#
// C# program for the above approach using System;using System.Collections.Generic;class GFG { // Function to print the // required N-th subset static void printSubset(int n, int k) { List<int> answer = new List<int>(); while(n > 0) { // Nearest power of 2<=N int p = (int)Math.Log(n,2); // Now insert k^p in the answer answer.Add((int)Math.Pow(k, p)); // update n n %= (int)Math.Pow(2, p); } // Print the ans in sorted order answer.Reverse(); foreach(int x in answer) { Console.Write(x + " "); } } // Driver code static void Main() { int n = 5; int k = 4; printSubset(n, k); }}// This code is contributed by divyeshrabadiya07. |
Javascript
<script>// Javascript program for the above approach // Function to print the // required N-th subset function printSubset(n, k){ var answer = []; while(n > 0) { // Nearest power of 2<=N var p = parseInt(Math.log2(n)); // Now insert k^p in the answer answer.push(Math.pow(k, p)); // update n n %= parseInt(Math.pow(2, p)); } // Print the ans in sorted order answer.sort(); //reverse(answer.begin(), answer.end()); for(var i=0;i<answer.length;i++) { document.write(answer[i] + " "); }}var n = 5;var k = 4;printSubset(n, k);//This code is contributed by SoumikMondal</script> |
Output
1 16
Time Complexity: O(logN)
Auxiliary Space: O(logN)
Approach:
- Initialize the count and x by 0. Also, a vector to store the elements of the subsets.
- Do the following while n is greater than 0.
- Set x = n & 1, for finding if the last bit of the number is set or not.
- Now Push element 3count into the subset if n is not 0.
- Reduce the number n by two with the help of right shifting by 1 unit.
- Increase the count value by 1.
- Finally, the elements in the array are the elements of the Nth subset.
Below is the implementation of the above approach:
C++
// C++ program to print subset// at the nth position ordered// by the sum of the elements#include <bits/stdc++.h>using namespace std;// Function to print the elements of // the subset at pos nvoid printsubset(int n,int k){ // Initialize count=0 and x=0 int count = 0, x = 0; // create a vector for // storing the elements // of subsets vector<int> vec; // doing until all the // set bits of n are used while (n) { x = n & 1; // this part is executed only // when the last bit is // set if (x) { vec.push_back(pow(k, count)); } // right shift the bit by one position n = n >> 1; // increasing the count each time by one count++; } // printing the values os elements for (int i = 0; i < vec.size(); i++) cout << vec[i] << " ";}// Driver Codeint main(){ int n = 7,k=4; printsubset(n,k); return 0;}// This code is contributed by shivkant |
Java
// Java program to print subset// at the nth position ordered// by the sum of the elementsimport java.util.*;import java.lang.*;class GFG{ // Function to print the // elements of the subset // at pos nstatic void printsubset(int n, int k){ // Initialize count=0 and x=0 int count = 0, x = 0; // Create a vector for // storing the elements // of subsets ArrayList<Integer> vec = new ArrayList<>(); // Doing until all the // set bits of n are used while (n != 0) { x = n & 1; // This part is executed only // when the last bit is // set if (x != 0) { vec.add((int)Math.pow(k, count)); } // Right shift the bit // by one position n = n >> 1; // Increasing the count // each time by one count++; } // Printing the values os elements for (int i = 0; i < vec.size(); i++) System.out.print(vec.get(i) + " ");}// Driver functionpublic static void main (String[] args) { int n = 7, k = 4; printsubset(n, k);}}// This code is contributed by offbeat |
Python3
# Python3 program to print subset# at the nth position ordered# by the sum of the elementsimport math# Function to print the elements of # the subset at pos ndef printsubset(n, k): # Initialize count=0 and x=0 count = 0 x = 0 # Create a vector for # storing the elements # of subsets vec = [] # Doing until all the # set bits of n are used while (n > 0): x = n & 1 # This part is executed only # when the last bit is # set if (x): vec.append(pow(k, count)) # Right shift the bit by one position n = n >> 1 # Increasing the count each time by one count += 1 # Printing the values os elements for item in vec: print(item, end = " ")# Driver Coden = 7k = 4printsubset(n, k)# This code is contributed by Stream_Cipher |
C#
// C# program to print subset// at the nth position ordered// by the sum of the elementsusing System.Collections.Generic; using System;class GFG{// Function to print the // elements of the subset // at pos nstatic void printsubset(int n, int k){ // Initialize count=0 and x=0 int count = 0, x = 0; // Create a vector for // storing the elements // of subsets List<int> vec = new List<int>(); // Doing until all the // set bits of n are used while (n != 0) { x = n & 1; // This part is executed only // when the last bit is // set if (x != 0) { vec.Add((int)Math.Pow(k, count)); } // Right shift the bit // by one position n = n >> 1; // Increasing the count // each time by one count++; } // Printing the values os elements for(int i = 0; i < vec.Count; i++) Console.Write(vec[i] + " ");}// Driver codepublic static void Main () { int n = 7, k = 4; printsubset(n, k);}}// This code is contributed by Stream_Cipher |
Javascript
<script> // Javascript program to print subset // at the nth position ordered // by the sum of the elements // Function to print the // elements of the subset // at pos n function printsubset(n, k) { // Initialize count=0 and x=0 let count = 0, x = 0; // Create a vector for // storing the elements // of subsets let vec = []; // Doing until all the // set bits of n are used while (n != 0) { x = n & 1; // This part is executed only // when the last bit is // set if (x != 0) { vec.push(Math.pow(k, count)); } // Right shift the bit // by one position n = n >> 1; // Increasing the count // each time by one count++; } // Printing the values os elements for(let i = 0; i < vec.length; i++) document.write(vec[i] + " "); } let n = 7, k = 4; printsubset(n, k);</script> |
Output
1 4 16
Time Complexity: O(log2N)
Auxiliary Space: O(log2N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
