Dados dos enteros X y S , la tarea es construir una secuencia de enteros distintos del rango [1, X] tal que la suma del valor 2 K sea igual a S , donde K es la posición del primer bit establecido desde el final ( indexación basada en 0 ) de la representación binaria de cada elemento es S.
Ejemplos:
Entrada: X = 3, S = 4
Salida: 2 3 1
Explicación:
La suma de 2 K para cada elemento del conjunto es la siguiente:
Para 2, es 2^1 = 2.
Para 3, es 2^0 = 1.
Para 1, es 2^0 = 1.
Por lo tanto, la suma requerida = 2 + 1 + 1 = 4, que es igual a S.Entrada: X = 1, S = 5
Salida: -1
Enfoque: el problema se puede resolver utilizando un enfoque codicioso . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos lowBit, para almacenar el valor de 2 K para cualquier número, donde K es la posición del primer bit establecido desde el final de la representación binaria de cada elemento .
- Inserte todos los valores de lowBit para todos los números en el rango [1, X] en un vector de pares V para emparejar los números junto con sus valores de lowBit . El valor de lowBit(X) se puede obtener mediante log2(N & -N) + 1 .
- Ordene el vector en orden inverso para obtener el lowBit máximo al principio.
- Inicialice una array , digamos ans[] , para almacenar el conjunto requerido y un número entero, digamos ansSum, para almacenar la suma actual de valores lowBit .
- Recorra el vector V y realice los siguientes pasos:
- Compruebe si (ansSum+v[i].first) <= S , luego agregue el valor de v[i].second a la array ans[] y actualice ansSum .
- Si ansSum es igual a la suma dada S, entonces salga del bucle e imprima la array resultante ans[] como resultado.
- Si se encuentra que ansSum no es igual a S, imprima “-1” .
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 calculate the lowest
// set bit of any number N
int lowBit(int N)
{
return log2(N & -N) + 1;
}
// Function to generate the sequence
// which adds up to sum on raising 2
// to the power of lowest set bit
// of all integers from the sequence
void find_set(int X, int sum)
{
// Stores the lowBit value
vector<pair<int, int> > v;
// Traverse through 1 to X and
// insert all the lowBit value
for (int i = 1; i <= X; i++) {
pair<int, int> aux;
aux.first = lowBit(i);
aux.second = i;
v.push_back(aux);
}
// Sort vector in reverse manner
sort(v.rbegin(), v.rend());
bool check = false;
// Store all our set values
vector<int> ans;
// Stores the current
// summation of lowBit
int ansSum = 0;
// Traverse vector v
for (int i = 0; i < v.size(); i++) {
// Check if ansSum+v[i].first
// is at most sum
if (ansSum + v[i].first <= sum) {
// Add to the ansSum
ansSum += v[i].first;
ans.push_back(v[i].second);
}
// If ansSum is same as the sum,
// then break from loop
if (ansSum == sum) {
check = true;
break;
}
}
// If check is false, no such
// sequence can be obtained
if (!check) {
cout << "-1";
return;
}
// Otherwise, print the sequence
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
}
// Driver Code
int main()
{
int X = 3, S = 4;
// Generate and print
// the required sequence
find_set(X, S);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
// User defined Pair class
class Pair {
int x;
int y;
// Constructor
public Pair(int x, int y)
{
this.x = x;
this.y = y;
}
}
// class to define user defined conparator
class Compare
{
static void compare(Pair arr[], int n)
{
// Comparator to sort the pair according to second element
Arrays.sort(arr, new Comparator<Pair>() {
@Override public int compare(Pair p1, Pair p2)
{
return p1.x - p2.x;
}
});
}
}
// Driver class
class GFG
{
// Function to calculate the lowest
// set bit of any number N
static int lowBit(int N)
{
return (int)(Math.log(N & -N) / Math.log(2)) + 1;
}
// Function to generate the sequence
// which adds up to sum on raising 2
// to the power of lowest set bit
// of all integers from the sequence
static void find_set(int X, int sum)
{
// Stores the lowBit value
Pair v[] = new Pair[X];
// Traverse through 1 to X and
// insert all the lowBit value
for (int i = 0; i < X; i++)
{
Pair aux = new Pair(lowBit(i + 1), i + 1);
v[i] = aux;
}
// Sort vector in reverse manner
Compare obj = new Compare();
obj.compare(v, X);
int j = X - 1;
for(int i = 0; i < X / 2; i++)
{
Pair temp = v[i];
v[i] = v[j];
v[j] = temp;
j--;
}
boolean check = false;
// Store all our set values
Vector<Integer> ans = new Vector<Integer>();
// Stores the current
// summation of lowBit
int ansSum = 0;
// Traverse vector v
for (int i = 0; i < X; i++) {
// Check if ansSum+v[i].first
// is at most sum
if (ansSum + v[i].x <= sum) {
// Add to the ansSum
ansSum += v[i].x;
ans.add(v[i].y);
}
// If ansSum is same as the sum,
// then break from loop
if (ansSum == sum) {
check = true;
break;
}
}
// If check is false, no such
// sequence can be obtained
if (!check)
{
System.out.println("-1");
return;
}
// Otherwise, print the sequence
for (int i = 0; i < ans.size(); i++)
{
System.out.print(ans.get(i) + " ");
}
}
// Driver code
public static void main(String[] args)
{
int X = 3, S = 4;
// Generate and print
// the required sequence
find_set(X, S);
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program for the above approach
from math import log2, ceil, floor
# Function to calculate the lowest
# set bit of any number N
def lowBit(N):
return log2(N & -N) + 1
# Function to generate the sequence
# which adds up to sum on raising 2
# to the power of lowest set bit
# of all integers from the sequence
def find_set(X, sum):
# Stores the lowBit value
v = []
# Traverse through 1 to X and
# insert all the lowBit value
for i in range(1, X + 1):
aux = [0, 0]
aux[0] = lowBit(i)
aux[1] = i
v.append(aux)
# Sort vector in reverse manner
v = sorted(v)[::-1]
check = False
# Store all our set values
ans = []
# Stores the current
# summation of lowBit
ansSum = 0
# Traverse vector v
for i in range(len(v)):
# Check if ansSum+v[i][0]
# is at most sum
if (ansSum + v[i][0] <= sum):
# Add to the ansSum
ansSum += v[i][0]
ans.append(v[i][1])
# If ansSum is same as the sum,
# then break from loop
if (ansSum == sum):
check = True
break
# If check is false, no such
# sequence can be obtained
if (not check):
print("-1")
return
# Otherwise, print the sequence
for i in range(len(ans)):
print(ans[i], end = " ")
# Driver Code
if __name__ == '__main__':
X, S = 3, 4
# Generate and pr
# the required sequence
find_set(X, S)
# 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 calculate the lowest
// set bit of any number N
static int lowBit(int N)
{
return (int)(Math.Log(N & -N, 2)) + 1;
}
// Function to generate the sequence
// which adds up to sum on raising 2
// to the power of lowest set bit
// of all integers from the sequence
static void find_set(int X, int sum)
{
// Stores the lowBit value
List<Tuple<int, int>> v = new List<Tuple<int, int>>();
// Traverse through 1 to X and
// insert all the lowBit value
for (int i = 1; i <= X; i++) {
Tuple<int, int> aux = new Tuple<int, int>(lowBit(i), i);
v.Add(aux);
}
// Sort vector in reverse manner
v.Sort();
v.Reverse();
bool check = false;
// Store all our set values
List<int> ans = new List<int>();
// Stores the current
// summation of lowBit
int ansSum = 0;
// Traverse vector v
for (int i = 0; i < v.Count; i++) {
// Check if ansSum+v[i].first
// is at most sum
if (ansSum + v[i].Item1 <= sum) {
// Add to the ansSum
ansSum += v[i].Item1;
ans.Add(v[i].Item2);
}
// If ansSum is same as the sum,
// then break from loop
if (ansSum == sum) {
check = true;
break;
}
}
// If check is false, no such
// sequence can be obtained
if (!check) {
Console.Write("-1");
return;
}
// Otherwise, print the sequence
for (int i = 0; i < ans.Count; i++) {
Console.Write(ans[i] + " ");
}
}
// Driver code
static void Main()
{
int X = 3, S = 4;
// Generate and print
// the required sequence
find_set(X, S);
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// Javascript program for the above approach
// Function to calculate the lowest
// set bit of any number N
function lowBit(N) {
return Math.log2(N & -N) + 1;
}
// Function to generate the sequence
// which adds up to sum on raising 2
// to the power of lowest set bit
// of all integers from the sequence
function find_set(X, sum) {
// Stores the lowBit value
let v = [];
// Traverse through 1 to X and
// insert all the lowBit value
for (let i = 1; i <= X; i++) {
let aux = [];
aux[0] = lowBit(i);
aux[1] = i;
v.push(aux);
}
// Sort vector in reverse manner
v.sort((a, b) => a[0] - b[0]).reverse();
let check = false;
// Store all our set values
let ans = [];
// Stores the current
// summation of lowBit
let ansSum = 0;
// Traverse vector v
for (let i = 0; i < v.length; i++) {
// Check if ansSum+v[i][0]
// is at most sum
if (ansSum + v[i][0] <= sum) {
// Add to the ansSum
ansSum += v[i][0];
ans.push(v[i][1]);
}
// If ansSum is same as the sum,
// then break from loop
if (ansSum == sum) {
check = true;
break;
}
}
// If check is false, no such
// sequence can be obtained
if (!check) {
document.write("-1");
return;
}
// Otherwise, print the sequence
for (let i = 0; i < ans.length; i++) {
document.write(ans[i] + " ");
}
}
// Driver Code
let X = 3, S = 4;
// Generate and print
// the required sequence
find_set(X, S);
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
2 3 1
Complejidad temporal: O(X)
Espacio auxiliar: O(X)
Publicación traducida automáticamente
Artículo escrito por kothawade29 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA