# Convert 0 to N by adding 1 or multiplying by 2 in minimum steps

Given a positive integer **N**, the task is to find the minimum number of addition operations required to convert the number **0** to **N** such that in each operation any number can be **multiplied by 2** or **add the value 1 to it**.

**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 = 6Output:1Explanation:

Following are the operations performed to convert 0 to 6:

Add 1 –> 0 + 1 = 1.

Multiply 2 –> 1 * 2 = 2.

Add 1 –> 2 + 1 = 3.

Mulitply 2 –> 3 * 2 = 6.

Therefore number of addition operations = 2.

Input:N = 3Output:2

**Approach:** This problem can be solved by using the Bit Manipulation technique. In binary number representation of **N**, while operating each bit whenever **N** becomes odd (that means the least significant bit of **N** is set) then perform the **addition operation**. Otherwise, **multiply by 2**. The final logic to the given problem is to find the number of set bits in N.

Below is the implementation of the above approach:

## C++

`// C++ program for above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to count number of` `// set bits in N` `int` `minimumAdditionOperation(` ` ` `unsigned ` `long` `long` `int` `N)` `{` ` ` `// Stores the count of set bits` ` ` `int` `count = 0;` ` ` `while` `(N) {` ` ` `// If N is odd, then it` ` ` `// a set bit` ` ` `if` `(N & 1 == 1) {` ` ` `count++;` ` ` `}` ` ` `N = N >> 1;` ` ` `}` ` ` `// Return the result` ` ` `return` `count;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `N = 6;` ` ` `cout << minimumAdditionOperation(N);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.io.*;` `class` `GFG {` ` ` `// Function to count number of` ` ` `// set bits in N` ` ` `static` `int` `minimumAdditionOperation(` `int` `N)` ` ` `{` ` ` `// Stores the count of set bits` ` ` `int` `count = ` `0` `;` ` ` `while` `(N > ` `0` `) {` ` ` `// If N is odd, then it` ` ` `// a set bit` ` ` `if` `(N % ` `2` `== ` `1` `) {` ` ` `count++;` ` ` `}` ` ` `N = N >> ` `1` `;` ` ` `}` ` ` `// Return the result` ` ` `return` `count;` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `int` `N = ` `6` `;` ` ` `System.out.println(minimumAdditionOperation(N));` ` ` `}` `}` `// This code is contributed by dwivediyash` |

## Python3

`# python program for above approach` `# Function to count number of` `# set bits in N` `def` `minimumAdditionOperation(N):` ` ` `# Stores the count of set bits` ` ` `count ` `=` `0` ` ` `while` `(N):` ` ` `# If N is odd, then it` ` ` `# a set bit` ` ` `if` `(N & ` `1` `=` `=` `1` `):` ` ` `count ` `+` `=` `1` ` ` `N ` `=` `N >> ` `1` ` ` `# Return the result` ` ` `return` `count` `# Driver Code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` `N ` `=` `6` ` ` `print` `(minimumAdditionOperation(N))` ` ` `# This code is contributed by rakeshsahni.` |

## C#

`// C# program for above approach` `using` `System;` `public` `class` `GFG{` ` ` ` ` `// Function to count number of` ` ` `// set bits in N` ` ` `static` `int` `minimumAdditionOperation(` `int` `N)` ` ` `{` ` ` ` ` `// Stores the count of set bits` ` ` `int` `count = 0;` ` ` ` ` `while` `(N != 0) {` ` ` ` ` `// If N is odd, then it` ` ` `// a set bit` ` ` `if` `((N & 1) == 1) {` ` ` `count++;` ` ` `}` ` ` `N = N >> 1;` ` ` `}` ` ` ` ` `// Return the result` ` ` `return` `count;` ` ` `}` ` ` ` ` `// Driver Code` ` ` `static` `public` `void` `Main (){` ` ` `int` `N = 6;` ` ` `Console.Write(minimumAdditionOperation(N));` ` ` ` ` `}` `}` `// This code is contributed by AnkThon` |

## Javascript

`<script>` `// Javascript program for above approach` `// Function to count number of` `// set bits in N` `function` `minimumAdditionOperation(N)` `{` ` ` `// Stores the count of set bits` ` ` `let count = 0;` ` ` `while` `(N)` ` ` `{` ` ` ` ` `// If N is odd, then it` ` ` `// a set bit` ` ` `if` `(N & (1 == 1)) {` ` ` `count++;` ` ` `}` ` ` `N = N >> 1;` ` ` `}` ` ` `// Return the result` ` ` `return` `count;` `}` `// Driver Code` `let N = 6;` `document.write(minimumAdditionOperation(N));` `// This code is contributed by saurabh_jaiswal.` `</script>` |

**Output:**

2

**Time Complexity:** O(log N)**Auxiliary Space:** O(1)