Sum of maximum and minimum of Kth subset ordered by increasing subset sum

0 0 5 minutes read

Given an integer N and a set of all non-negative powers of N as S = {N⁰, N¹, N², N³, … }, arrange all non-empty subsets of S in increasing order of subset-sum. The task is to find the sum of the greatest and smallest elements of the K^th subset from that ordering.

Examples:

Input: N = 4, K = 3
Output: 5
Explanation:
S = {1, 4, 16, 64, …}.
Therefore, the non-empty subsets arranged in increasing order of their sum = {{1}, {4}, {1, 4}, {16}, {1, 16}, {4, 16}, {1, 4, 16}………}.
So the elements of the subset in K^th(3^rd) subset are {1, 4}. So the sum of the greatest and smallest elements of this subset = (4 + 1) = 5.

Input: N = 3, K = 4
Output: 18
Explanation:
S = {1, 3, 9, 27, 81, …}.
Therefore, the non-empty subsets arranged in increasing order of their sum = {{1}, {3}, {1, 3}, {9}, {1, 9}, {3, 9}, {1, 3, 9} ……..}.
So the element in the subset at 4^th position is {9}. So the sum of the greatest and smallest elements of this subset = (9 + 9) = 18.

Approach: This approach is based on the concept of Power-set. Follow the steps below to solve the problem:

Generate the corresponding binary expression of the integer K (i.e., the position of the subset) in inverse order to maintain the increasing sum of elements in the subset.
Then calculate whether there will be an element in the subset at corresponding positions depending on the bits present in lst[] list at successive positions.
Iterate over the lst[] and if lst[i] is 0, then ignore that bit, otherwise (Nⁱ)*lst[i] will be in the K^th Subset num[].
Then the sum is calculated by taking the element of the num[] at position 0 and at the last position.
Print the resultant sum after the above steps.

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 sum of greatest
// and smallest element of Kth Subset
void sumofExtremes(int N, int K)
{
 
    // Stores the binary equivalent
    // of k in inverted order
    list<int> lst;
 
    while (K > 0)
    {
        lst.push_back(K % 2);
        K = K / 2;
    }
 
    // Stores the kth subset
    list<int> num;
 
    int x = 0;
 
    // Iterate over the list
    for(auto element : lst)
    {
         
        // If the element is non-zero
        if (element != 0) 
        {
            int a = pow(N, x);
            a = a * (element);
            num.push_back(a);
        }
        x++;
    }
     
    // Update S to length of num
    int s = num.size();
 
    // If length of the subset is 1
    if (s == 1)
 
        // Print twice of that element
        cout << (2 * num.front()) << "\n";
 
    // Print the sum of first and
    // last element
    else
        cout << num.front() + num.back();
}
 
// Driver Code
int main()
{
     
    // Given number N
    int N = 4;
 
    // Given position K
    int K = 6;
 
    sumofExtremes(N, K);
}
 
// This code is contributed by akhilsaini

Java

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG{
 
// Function to find the sum of greatest
// and smallest element of Kth Subset
public static void sumofExtremes(int N, int K)
{
     
    // Stores the binary equivalent
    // of k in inverted order
    List<Integer> lst = new ArrayList<Integer>();
 
    while (K > 0) 
    {
        lst.add(K % 2);
        K = K / 2;
    }
 
    // Stores the kth subset
    List<Integer> num = new ArrayList<Integer>();
 
    int x = 0;
 
    // Iterate over the list
    for(int element : lst)
    {
         
        // If the element is non-zero
        if (element != 0) 
        {
            int a = (int)Math.pow(N, x);
            a = a * (element);
            num.add(a);
        }
        x++;
    }
     
    // Update S to length of num
    int s = num.size();
 
    // If length of the subset is 1
    if (s == 1)
 
        // Print twice of that element
        System.out.println(2 * num.get(0));
 
    // Print the sum of first and
    // last element
    else
        System.out.println(num.get(0) + 
                           num.get(s - 1));
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given number N
    int N = 4;
 
    // Given position K
    int K = 6;
 
    // Function call
    sumofExtremes(N, K);
}
}
 
// This code is contributed by akhilsaini

Python3

# Python3 program for the above approach
 
# Function to find the sum of greatest
# and smallest element of Kth Subset
def sumofExtremes(N, K):
 
    # Stores the binary equivalent
    # of k in inverted order
    lst = []
 
    while K > 0:
        lst.append(K % 2)
        K = K//2
 
    # Stores the kth subset
    num = []
     
    # Iterate over the list
    for i in range(0, len(lst)):
         
        # If the element is non-zero
        if(lst[i] != 0):
            a = N**i
            a = a * lst[i]
            num.append(a)
     
    # Update S to length of num
    s = len(num)
 
    # If length of the subset is 1
    if(s == 1):
 
        # Print twice of that element
        print(2 * num[0])
 
 
    # Print the sum of first and
    # last element
    else:
        print(num[0] + num[s - 1])
 
 
# Driver Code
 
# Given number N
N = 4
 
# Given position K
K = 6
 
# Function Call
sumofExtremes(N, K)

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the sum of greatest
// and smallest element of Kth Subset
public static void sumofExtremes(int N, int K)
{
     
    // Stores the binary equivalent
    // of k in inverted order
    List<int> lst = new List<int>();
 
    while (K > 0) 
    {
        lst.Add(K % 2);
        K = K / 2;
    }
 
    // Stores the kth subset
    List<int> num = new List<int>();
 
    // Iterate over the list
    for(int i = 0; i < lst.Count; i++)
    {
         
        // If the element is non-zero
        if (lst[i] != 0) 
        {
            int a = (int)Math.Pow(N, i);
            a = a * (lst[i]);
            num.Add(a);
        }
    }
     
    // Update S to length of num
    int s = num.Count;
 
    // If length of the subset is 1
    if (s == 1)
 
        // Print twice of that element
        Console.WriteLine(2 * num[0]);
 
    // Print the sum of first and
    // last element
    else
        Console.WriteLine(num[0] + num[s - 1]);
}
 
// Driver Code
static public void Main()
{
     
    // Given number N
    int N = 4;
 
    // Given position K
    int K = 6;
 
    // Function call
    sumofExtremes(N, K);
}
}
 
// This code is contributed by akhilsaini

Javascript

<script>
// Javascript program for the above approach
 
// Function to find the sum of greatest
// and smallest element of Kth Subset
function sumofExtremes(N, K)
{
 
    // Stores the binary equivalent
    // of k in inverted order
    let lst = [];
 
    while (K > 0)
    {
        lst.push(K % 2);
        K = Math.floor(K / 2);
    }
 
    // Stores the kth subset
    let num = [];
 
    let x = 0;
 
    // Iterate over the list
    for(let element of lst)
    {
         
        // If the element is non-zero
        if (element != 0)
        {
            let a = Math.pow(N, x);
            a = a * (element);
            num.push(a);
        }
        x++;
    }
     
    // Update S to length of num
    let s = num.length;
 
    // If length of the subset is 1
    if (s == 1)
 
        // Print twice of that element
        document.write((2 * num[0]) + "+");
 
    // Print the sum of first and
    // last element
    else
        document.write(num[0] + num[num.length - 1]);
}
 
// Driver Code
     
    // Given number N
    let N = 4;
 
    // Given position K
    let K = 6;
 
    sumofExtremes(N, K);
 
 
// This code is contributed by gfgking
</script>

Output:

Time Complexity: O(log K)
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!