Given a range of number [L, R], the task is to find all numbers X in the given range such that X = sum of digits raised to setbit count of X i.e., if there are N setbits in binary representation of X and X = x1x2x3… then X = (x1)N + (x2)N + (x3)N + . . .
Examples:
Input: L = 0, R = 10000
Output: 1, 2, 4, 8, 4150, 9474
Explanation: For 2 (binary = 10): setbit count = 1. and 2 = 2^1.
So this is a required number. Same for the other numbers also.Input: L = 10000, R = 1000000
Output: -1
Explanation: There are no such numbers in the given range.
Approach: The given problem can be solved by checking for all numbers in the range [L, R] and if they satisfy the condition or not. It can be done with the help of Brian Kernighan’s Algorithm.
Follow the steps mentioned below to solve the problem.
- Run a loop from L to R and in every iteration check the number is index number or not.
- First calculate number of set bits in the decimal number from its binary representation.
- Then, Initialize Original = N, Res = 0, Index = Count of Set bits.
- Run a loop while N > 0
- Find last digit from the number say (L),
- Add LIndex to Res.
- Remove last digit from the number.
- If Original = Res, this will be one of the required numbers.
Below is the implementation of the above approach:
C++
// 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 numberint 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 notbool 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 numbersvector<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 Codeint 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
// Java program for the above approachimport 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. |
Python3
# Python code to implement the above approach# Function to return Number of# set bits in any decimal numberdef countSetBits(N): Count = 0 while (N): N = N & (N - 1) Count += 1 return Count# Function to check whether the# number is index number or notdef 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 numbersdef 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 CodeL,R = 0,10000# Function callres = findNum(L, R) if(len(res)==0): print(-1) for x in res: print(x , end = " ")# This code is contributed by shinjanpatra |
C#
// C# program for the above approachusing 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 |
Javascript
<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> |
Output
1 2 4 8 4150 9474
Time Complexity: O(R * d) where d is the maximum number of bits in a number
Auxiliary Space: O(1)
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!
Share your thoughts in the comments
