Suma del máximo y mínimo del K-ésimo subconjunto ordenado por suma de subconjunto creciente

Posted on by Rudeus Greyrat

Dado un número entero N y un conjunto de todas las potencias no negativas de N como S = {N 0 , N 1 , N 2 , N 3 , … } , organice todos los subconjuntos no vacíos de S en orden creciente de suma de subconjuntos. La tarea es encontrar la suma de los elementos más grandes y más pequeños del K -ésimo subconjunto de esa ordenación.

Ejemplos:

Entrada: N = 4, K = 3
Salida: 5
Explicación: 
S = {1, 4, 16, 64, …}.
Por lo tanto, los subconjuntos no vacíos dispuestos en orden creciente de su suma = {{1}, {4}, {1, 4}, {16}, {1, 16}, {4, 16}, {1, 4 , dieciséis}………}. 
Entonces, los elementos del subconjunto en el Kth (3 rd ) subconjunto son {1, 4}. Entonces, la suma de los elementos más grandes y más pequeños de este subconjunto = (4 + 1) = 5.

Entrada: N = 3, K = 4
Salida: 18
Explicación:
S = {1, 3, 9, 27, 81, …}.
Por lo tanto, los subconjuntos no vacíos ordenados en orden creciente de su suma = {{1}, {3}, {1, 3}, {9}, {1, 9}, {3, 9}, {1, 3 , 9} ……..}.
Entonces, el elemento en el subconjunto en la 4ª posición es {9}. Entonces, la suma de los elementos más grandes y más pequeños de este subconjunto = (9 + 9) = 18.

 

Enfoque: Este enfoque se basa en el concepto de Power-set . Siga los pasos a continuación para resolver el problema:

  1. Genere la expresión binaria correspondiente del entero K (es decir, la posición del subconjunto) en orden inverso para mantener la suma creciente de elementos en el subconjunto.
  2. Luego calcule si habrá un elemento en el subconjunto en las posiciones correspondientes dependiendo de los bits presentes en la lista lst[] en las posiciones sucesivas.
  3. Itere sobre el lst[] y si lst[i] es 0 , entonces ignore ese bit, de lo contrario ( N i )*lst[i] estará en el Kth Subset num [ ] .
  4. Luego, la suma se calcula tomando el elemento de num[] en la posición 0 y en la última posición.
  5. Imprime la suma resultante después de los pasos anteriores.

A continuación se muestra la implementación del enfoque anterior:

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>
Producción: 

20

 

Complejidad temporal: O(log K)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por abhirup45 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *