Encuentre números en L a R que es lo mismo que la suma de dígitos elevados para establecer el conteo de bits

Dado un rango de números [L, R] , la tarea es encontrar todos los números X en el rango dado, de modo que X = suma de dígitos elevados al recuento de bits establecidos de X   , es decir, si hay N bits establecidos en representación binaria de X y X = X ₁ X ₂ X ₃ … entonces X = (X ₁ ) ^N + (X ₂ ) ^N  + (X ₃ ) ^N  + . . .

Ejemplos:  

Entrada: L = 0, R = 10000
Salida: 1, 2, 4, 8, 4150, 9474
Explicación: Para 2 (binario = 10): número de bits definidos = 1 y 2 = 2^1.
Así que este es un número requerido. Lo mismo para los otros números también.

Entrada: L = 10000, R = 1000000
Salida: -1
Explicación: No hay tales números en el rango dado.

Enfoque: el problema dado se puede resolver verificando todos los números en el rango [L, R] y si cumplen la condición o no. Se puede hacer con la ayuda del Algoritmo de Brian Kernighan .

Siga los pasos que se mencionan a continuación para resolver el problema.

• Ejecute un ciclo de L a R y en cada iteración verifique que el número sea un número de índice o no.
• Primero calcule el número de bits establecidos en el número decimal a partir de su representación binaria.
• Luego, Inicializar original = N , Res = 0 , Índice = Recuento de bits establecidos .
• Ejecutar un ciclo mientras N > 0
  • Encuentre el último dígito del número, digamos ( L ),
  • Añadir ^Índice L a Res.
  • Elimina el último dígito del número.
• Si Original = Res , este será uno de los números requeridos.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
 
// Function to return Number of
// set bits in any decimal number
int countSetBits(ll N)
{
    int Count = 0;
    while (N) {
        N = N & (N - 1);
        Count++;
    }
    return Count;
}
 
// Function to check whether the
// number is index number or not
bool check(int Index, ll N)
{
    ll Original = N, Res = 0;
   
    if(N == 0)
      return false;
   
    while (N != 0) {
        int L = N % 10;
        Res += pow(L, Index);
        N = N / 10;
    }
    return Original == Res;
}
 
// Function to find the numbers
vector<int> findNum(int l, int r)
{
    // Vector to store the numbers
    vector<int> ans;
 
    for (ll i = l; i <= r; i++) {
        int BitCount = countSetBits(i);
        if (check(BitCount, i))
            ans.push_back(i);
    }
    return ans;
}
 
// Driver Code
int main()
{
    int L = 0, R = 10000;
 
    // Function call
    vector<int> res = findNum(L, R);
           
    if(res.size()==0)
        cout << -1 << endl;
   
    for (int x : res)
        cout << x << " ";
   
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG {
 
  // Function to return Number of
  // set bits in any decimal number
  static int countSetBits(long N)
  {
    int Count = 0;
    while (N != 0) {
      N = N & (N - 1);
      Count++;
    }
    return Count;
  }
 
  // Function to check whether the
  // number is index number or not
  static boolean check(int Index, long N)
  {
    long Original = N, Res = 0;
 
    if(N == 0)
      return false;
 
    while (N != 0) {
      long L = N % 10;
      Res += Math.pow(L, Index);
      N = N / 10;
    }
    return Original == Res;
  }
 
  // Function to find the numbers
  static Vector<Integer> findNum(int l, int r)
  {
 
    // Vector to store the numbers
    Vector<Integer> ans = new Vector<Integer>();
 
    for (int i = l; i <= r; i++) {
      int BitCount = countSetBits(i);
      if (check(BitCount, i))
        ans.add(i);
    }
    return ans;
  }
 
  // Driver Code
  public static void main (String[] args) {   
    int L = 0, R = 10000;
 
    // Function call
    Vector<Integer> res = findNum(L, R);
 
    if(res.size()==0)
      System.out.println(-1);
 
    res.forEach((x) -> System.out.print(x + " "));
  }
}
 
// This code is contributed by hrithikgarg03188.

# Python code to implement the above approach
 
# Function to return Number of
# set bits in any decimal number
def countSetBits(N):
    Count = 0
    while (N):
        N = N & (N - 1)
        Count += 1
 
    return Count
 
# Function to check whether the
# number is index number or not
def check(Index, N):
 
    Original,Res = N,0
   
    if(N == 0):
      return False
   
    while (N != 0):
        L = N % 10
        Res += pow(L, Index)
        N = N // 10
 
    return Original == Res
 
# Function to find the numbers
def findNum(l, r):
 
    # Vector to store the numbers
    ans = []
 
    for i in range(l,r + 1):
        BitCount = countSetBits(i)
        if (check(BitCount, i)):
            ans.append(i)
 
    return ans
 
# Driver Code
L,R = 0,10000
 
# Function call
res = findNum(L, R)
   
if(len(res)==0):
    print(-1)
   
for x in res:
    print(x , end = " ")
 
# This code is contributed by shinjanpatra

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
  // Function to return Number of
  // set bits in any decimal number
  public static int countSetBits(long N)
  {
    int Count = 0;
    while (N != 0) {
      N = N & (N - 1);
      Count++;
    }
    return Count;
  }
 
  // Function to check whether the
  // number is index number or not
  public static bool check(int Index, long N)
  {
    long Original = N, Res = 0;
 
    if(N == 0)
      return false;
 
    while (N != 0) {
      long L = N % 10;
      Res += (long)Math.Pow(L, Index);
      N = N / 10;
    }
    return Original == Res;
  }
 
  // Function to find the numbers
  public static List<int> findNum(int l, int r)
  {
 
    // Vector to store the numbers
    List<int> ans = new List<int>();
 
    for (int i = l; i <= r; i++) {
      int BitCount = countSetBits(i);
      if (check(BitCount, i))
        ans.Add(i);
    }
    return ans;
  }
 
  // Driver Code
  public static void Main (String[] args) {   
    int L = 0, R = 10000;
 
    // Function call
    List<int> res = findNum(L, R);
 
    if(res.Count == 0)
      Console.WriteLine(-1);
 
    for (int i = 0; i < res.Count; i++)
      Console.Write(res[i] + " ");
  }
}
 
// This code is contributed by phasing17

<script>
    // JavaScript program for the above approach
 
 
    // Function to return Number of
    // set bits in any decimal number
    const countSetBits = (N) => {
        let Count = 0;
        while (N) {
            N = N & (N - 1);
            Count++;
        }
        return Count;
    }
 
    // Function to check whether the
    // number is index number or not
    const check = (Index, N) => {
        let Original = N, Res = 0;
        while (N != 0) {
            let L = N % 10;
            Res += Math.pow(L, Index);
            N = parseInt(N / 10);
        }
        return Original == Res;
    }
 
    // Function to find the numbers
    const findNum = (l, r) => {
        // Vector to store the numbers
        let ans = [];
 
        for (let i = l; i <= r; i++) {
            let BitCount = countSetBits(i);
            if (check(BitCount, i))
                ans.push(i);
        }
        return ans;
    }
 
    // Driver Code
 
    let L = 0, R = 10000;
 
    // Function call
    let res = findNum(L, R);
    for (let x in res)
        document.write(`${res[x]} `);
 
// This code is contributed by rakeshsahni
 
</script>

1 2 4 8 4150 9474 

Complejidad de tiempo : O(R * d) donde d es el número máximo de bits en un número
Espacio auxiliar : O(1)