Given a number X, the task is to find the minimum number N such that the total set bits of all numbers from 1 to n is at least X.
Examples:
Input: x = 5 Output: 4 Set bits in 1-> 1 Set bits in 2-> 1 Set bits in 3-> 2 Set bits in 4-> 1 Hence first four numbers add upto 5 Input: x = 20 Output: 11
Approach: Use binary search to get the minimum most number whose sum of bits till N is at least X. At the start, low is 0, and high is initialized according to the constraint. Check if the count of set bits is at least X, every time it is, change high to mid-1, else change it to mid+1. Every time we do high = mid-1, store the minimal of answer.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;#define INF 99999#define size 10// Function to count sum of set bits// of all numbers till Nint getSetBitsFromOneToN(int N){ int two = 2, ans = 0; int n = N; while (n) { ans += (N / two) * (two >> 1); if ((N & (two - 1)) > (two >> 1) - 1) ans += (N & (two - 1)) - (two >> 1) + 1; two <<= 1; n >>= 1; } return ans;}// Function to find the minimum numberint findMinimum(int x){ int low = 0, high = 100000; int ans = high; // Binary search for the lowest number while (low <= high) { // Find mid number int mid = (low + high) >> 1; // Check if it is atleast x if (getSetBitsFromOneToN(mid) >= x) { ans = min(ans, mid); high = mid - 1; } else low = mid + 1; } return ans;}// Driver Codeint main(){ int x = 20; cout << findMinimum(x);return 0;} |
Java
// Java implementation of the above approachimport java.util.*;class solution{static int INF = 99999;static int size = 10;// Function to count sum of set bits// of all numbers till Nstatic int getSetBitsFromOneToN(int N){ int two = 2, ans = 0; int n = N; while (n!=0) { ans += (N / two) * (two >> 1); if ((N & (two - 1)) > (two >> 1) - 1) ans += (N & (two - 1)) - (two >> 1) + 1; two <<= 1; n >>= 1; } return ans;}// Function to find the minimum numberstatic int findMinimum(int x){ int low = 0, high = 100000; int ans = high; // Binary search for the lowest number while (low <= high) { // Find mid number int mid = (low + high) >> 1; // Check if it is atleast x if (getSetBitsFromOneToN(mid) >= x) { ans = Math.min(ans, mid); high = mid - 1; } else low = mid + 1; } return ans;}// Driver Codepublic static void main(String args[]){ int x = 20; System.out.println(findMinimum(x));}}//This code is contributed by // Shashank_Sharma |
Python3
# Python3 implementation of the # above approachINF = 99999size = 10# Function to count sum of set bits# of all numbers till Ndef getSetBitsFromOneToN(N): two, ans = 2, 0 n = N while (n > 0): ans += (N // two) * (two >> 1) if ((N & (two - 1)) > (two >> 1) - 1): ans += (N & (two - 1)) - (two >> 1) + 1 two <<= 1 n >>= 1 return ans# Function to find the minimum numberdef findMinimum(x): low = 0 high = 100000 ans = high # Binary search for the lowest number while (low <= high): # Find mid number mid = (low + high) >> 1 # Check if it is atleast x if (getSetBitsFromOneToN(mid) >= x): ans = min(ans, mid) high = mid - 1 else: low = mid + 1 return ans# Driver Codex = 20print(findMinimum(x))# This code is contributed by# Mohit kumar 29 |
C#
// C# implementation of the above approach using System ;class solution { static int INF = 99999; static int size = 10; // Function to count sum of set bits // of all numbers till N static int getSetBitsFromOneToN(int N) { int two = 2, ans = 0; int n = N; while (n!=0) { ans += (N / two) * (two >> 1); if ((N & (two - 1)) > (two >> 1) - 1) ans += (N & (two - 1)) - (two >> 1) + 1; two <<= 1; n >>= 1; } return ans; } // Function to find the minimum number static int findMinimum(int x) { int low = 0, high = 100000; int ans = high; // Binary search for the lowest number while (low <= high) { // Find mid number int mid = (low + high) >> 1; // Check if it is atleast x if (getSetBitsFromOneToN(mid) >= x) { ans = Math.Min(ans, mid); high = mid - 1; } else low = mid + 1; } return ans; } // Driver Code public static void Main() { int x = 20; Console.WriteLine(findMinimum(x)); } // This code is contributed by Ryuga} |
PHP
<?php// PHP implementation of the above approach// Function to count sum of set bits// of all numbers till Nfunction getSetBitsFromOneToN($N){ $two = 2; $ans = 0; $n = $N; while ($n) { $ans += (int)($N / $two) * ($two >> 1); if (($N & ($two - 1)) > ($two >> 1) - 1) $ans += ($N & ($two - 1)) - ($two >> 1) + 1; $two <<= 1; $n >>= 1; } return $ans;}// Function to find the minimum numberfunction findMinimum($x){ $low = 0; $high = 100000; $ans = $high; // Binary search for the lowest number while ($low <= $high) { // Find mid number $mid = ($low + $high) >> 1; // Check if it is atleast x if (getSetBitsFromOneToN($mid) >= $x) { $ans = min($ans, $mid); $high = $mid - 1; } else $low = $mid + 1; } return $ans;}// Driver Code$x = 20;echo findMinimum($x);// This code is contributed // by Sach_Code?> |
Javascript
<script>// Javascript implementation of the above approachconst INF = 99999;const size = 10;// Function to count sum of set bits// of all numbers till Nfunction getSetBitsFromOneToN(N){ let two = 2, ans = 0; let n = N; while (n) { ans += parseInt(N / two) * (two >> 1); if ((N & (two - 1)) > (two >> 1) - 1) ans += (N & (two - 1)) - (two >> 1) + 1; two <<= 1; n >>= 1; } return ans;}// Function to find the minimum numberfunction findMinimum(x){ let low = 0, high = 100000; let ans = high; // Binary search for the lowest number while (low <= high) { // Find mid number let mid = (low + high) >> 1; // Check if it is atleast x if (getSetBitsFromOneToN(mid) >= x) { ans = Math.min(ans, mid); high = mid - 1; } else low = mid + 1; } return ans;}// Driver Codelet x = 20;document.write(findMinimum(x));// This code is contributed by subhammahato348</script> |
Output:
11
Time Complexity: O(log N * log N), the getSetBitsFromOneToN will take logN time as we are using the bitwise right shift in each traversal which is equivalent to floor division with 2 in each traversal so the cost will be 1+1/2+1/4+….+1/2N which is equivalent to logN. We are using binary search and each time we are calling getSetBitsFromOneToN function. Binary Search also takes logN time as we decrement each time by floor division of 2. So, the effective cost of the program will be O(logN*logN).
Auxiliary Space: O(1), as we are not using any extra space.
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!
