We have an integer N. We need to express N as a sum of K integers such that by adding some(or all) of these integers we can get all the numbers in the range[1, N]. What is the minimum value of K?
Examples:
Input : N = 7 Output : 3 Explanation : Three integers are 1, 2, 4. By adding some(or all) of these groups we can get all number in the range 1 to N. 1; 2; 1+2=3; 4; 1+4=5; 2+4=6; 1+2+4=7 Input : N = 32 Output : 6 Explanation : Six integers are 1, 2, 4, 8, 16, 1.
1st we solve the problem for small numbers by hand.
n=1 : 1
n=2 : 1, 1
n=3 : 1, 2
n=4 : 1, 2, 1
n=5 : 1, 2, 2
n=6 : 1, 2, 3
n=7 : 1, 2, 4
n=8 : 1, 2, 4, 1
If we inspect this closely we can see that if 
then the integers are ![[1, 2, 4..., 2^{m-1}]](https://geeksforgeeks.org/wp-content/uploads/2023/10/dominic_rubhabha_quicklatex.com-5b26be19db881b35e2ab87bf5cd3975d_l3.png "Rendered by QuickLaTeX.com")
. Which is just another way of saying 
.So now we know for 
minimum value of K is m.
Now we inspect what happens for 
.For we just add a new integer 1 to our list of integers. Realize that for every number from 
we can increase the newly added integer by 1 and that will be the optimal list of integers. To verify look at N=4 to N=7, minimum K does not change; only the last integer is increased in each step.
Of course we can implement this in iterative manner in O(log N) time (by inserting successive powers of 2 in the list and the last element will be of the form N-(2^n-1)). But this is exactly same as finding the length of binary expression of N which also can be done in O(log N) time.
C++
// CPP program to find count of integers needed// to express all numbers from 1 to N.#include <bits/stdc++.h>using namespace std;// function to count length of binary expression of nint countBits(int n){ int count = 0; while (n) { count++; n >>= 1; } return count;}// Driver codeint main(){ int n = 32; cout << "Minimum value of K is = " << countBits(n) << endl; return 0;} |
Java
// Java program to find count of integers needed // to express all numbers from 1 to Nimport java.io.*;class GFG { // function to count length of binary expression of n static int countBits(int n) { int count = 0; while (n>0) { count++; n >>= 1; } return count; } // Driver code public static void main (String[] args) { int n = 32; System.out.println("Minimum value of K is = "+ countBits(n)); }} |
Python3
# Python3 program to find count of integers # needed to express all numbers from 1 to N. # function to count length of # binary expression of n def countBits(n): count = 0; while (n): count += 1; n >>= 1; return count; # Driver code n = 32; print("Minimum value of K is =", countBits(n)); # This code is contributed by mits |
C#
// C# program to find count of // integers needed to express all // numbers from 1 to Nusing System;class GFG{// function to count length of // binary expression of n static int countBits(int n) { int count = 0; while (n > 0) { count++; n >>= 1; } return count; } // Driver codestatic public void Main (){ int n = 32; Console.WriteLine("Minimum value of K is = "+ countBits(n));}}// This code is contributed// by Sach_Code |
PHP
<?php// PHP program to find count of integers // needed to express all numbers from 1 to N. // function to count length of // binary expression of n function countBits($n) { $count = 0; while ($n) { $count++; $n >>= 1; } return $count; } // Driver code $n = 32; echo "Minimum value of K is = ", countBits($n), "\n"; // This code is contributed by Sachin?> |
Javascript
<script>// Javascript program to find count of // integers needed to express all // numbers from 1 to N.// Function to count length of binary// expression of nfunction countBits(n){ var count = 0; while (n) { count++; n >>= 1; } return count;}// Driver codevar n = 32;document.write("Minimum value of K is = " + countBits(n)); // This code is contributed by rrrtnx</script> |
output:
Minimum value of K is = 6
Time Complexity: O(log n)
Auxiliary Space: O(1)
Please see count set bits for more efficient methods to count set bits in an integer.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
