Minimum numbers needed to express every integer below N as a sum
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 . 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 n int countBits( int n) { int count = 0; while (n) { count++; n >>= 1; } return count; } // Driver code int 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 N import 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 N using 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 code static 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 n function countBits(n) { var count = 0; while (n) { count++; n >>= 1; } return count; } // Driver code var 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.