# 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:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

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

Please see count set bits for more efficient methods to count set bits in an integer.