# Minimum number of given operations required to be performed to reduce N to 0

Given an integer **N**, the task is to reduce **N** to 0 in the minimum number of operations using the following operations any number of times:

- Change the rightmost (0
^{th}) bit in the binary representation of**N**. - Change the
**i**bit in the binary representation of^{th}**N**if the**(i-1)**bit is set to 1 and the^{th}**(i-2)**through^{th}**0**bits are set to 0.^{th}

**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 = 3Output:2Explanation:The binary representation of 3 is “11”.

“11″ → “01” with the 2nd operation since the 0th bit is 1.

“01″ → “00″ with the 1st operation.

Input:N = 6Output:4Explanation:The binary representation of 6 is “110”.

“110” → “010” with the 2nd operation since the 1st bit is 1 and 0th through 0th bits are 0.

“010” → “011” with the 1st operation.

“011” → “001” with the 2nd operation since the 0th bit is 1.

“001” → “000” with the 1st operation.

**Approach: **The idea is based on the following observations:

- 1 → 0 needs 1 operation.

2 → 0 i.e 10 → 11 → 01 → 0 needs 3 operations.

4 → 0 i.e 100 → 101 → 111 → 110 → 010 → 11 → 01 →0

Hence, it can be generalized for any power of 2 i.e, 2^{k}needs 2^{(k+1) }-1 operations. - If a → b requires k operation, b → a also requires k operation.

Intermediate numbers from 2^{n} to 2^{(n-1)} contain all numbers between 2^{n} and 2^{(n-1)}, which demonstrates that any given non-negative integer can be converted to 0. Let f(n) be a function to find the minimum number of operations required. The recurrence relation is:

f(n) = f(2^{k}) – f(n xor 2^{k}), where k = next bit of most significant bit of n.

The idea is to use recursion. Follow the steps below to solve the problem:

- Create a recursive function that takes a number
**N**as a parameter.- If the value of
**N**is equal to**0**, return**0**. - Else, find the highest power of 2 less than or equal to
**N**and store it in a variable**X**. - Store the value returned by recursively calling the function for
**(X^(X/2)^N)**in a variable**S**. - Add the value of
**X**to**S**and return it.

- If the value of

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find minimum` `// operations required to convert` `// N to 0` `int` `minimumOneBitOperations(` `int` `n, ` `int` `res = 0)` `{` ` ` `// Base Case` ` ` `if` `(n == 0)` ` ` `return` `res;` ` ` `// Store the highest power of 2` ` ` `// less than or equal to n` ` ` `int` `b = 1;` ` ` `while` `((b << 1) <= n)` ` ` `b = b << 1;` ` ` `// Return the result` ` ` `return` `minimumOneBitOperations(` ` ` `(b >> 1) ^ b ^ n, res + b);` `}` `// Driver Code` `int` `main()` `{` ` ` `// Given Input` ` ` `int` `N = 6;` ` ` `// Function call` ` ` `cout << minimumOneBitOperations(N);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `class` `GFG {` ` ` `// Function to find minimum` ` ` `// operations required to convert` ` ` `// N to 0` ` ` `public` `static` `int` `minimumOneBitOperations(` `int` `n, ` `int` `res)` ` ` `{` ` ` ` ` `// Base Case` ` ` `if` `(n == ` `0` `)` ` ` `return` `res;` ` ` `// Store the highest power of 2` ` ` `// less than or equal to n` ` ` `int` `b = ` `1` `;` ` ` `while` `((b << ` `1` `) <= n)` ` ` `b = b << ` `1` `;` ` ` `// Return the result` ` ` `return` `minimumOneBitOperations((b >> ` `1` `) ^ b ^ n, res + b);` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `main(String args[])` ` ` `{` ` ` ` ` `// Given Input` ` ` `int` `N = ` `6` `;` ` ` `// Function call` ` ` `System.out.println(minimumOneBitOperations(N, ` `0` `));` ` ` `}` `}` `// This code is contributed by gfgking.` |

## Python3

`# Python program for the above approach` `# Function to find minimum` `# operations required to convert` `# N to 0` `def` `minimumOneBitOperations(n, res):` ` ` ` ` `# Base case` ` ` `if` `n ` `=` `=` `0` `:` ` ` `return` `res` ` ` ` ` `# Store the highest power of 2` ` ` `# less than or equal to n ` ` ` `b ` `=` `1` ` ` `while` `(b << ` `1` `) <` `=` `n:` ` ` `b ` `=` `b << ` `1` ` ` ` ` `# Return the result` ` ` `return` `minimumOneBitOperations((b >> ` `1` `) ^ b ^ n, res ` `+` `b)` `# Driver code` `N ` `=` `6` `print` `(minimumOneBitOperations(N, ` `0` `))` `# This code is contributed by Parth Manchanda` |

## C#

`// C# program for the above approach` `using` `System;` `using` `System.Collections.Generic;` `class` `GFG{` `// Function to find minimum` `// operations required to convert` `// N to 0` `static` `int` `minimumOneBitOperations(` `int` `n, ` `int` `res)` `{` ` ` `// Base Case` ` ` `if` `(n == 0)` ` ` `return` `res;` ` ` `// Store the highest power of 2` ` ` `// less than or equal to n` ` ` `int` `b = 1;` ` ` `while` `((b << 1) <= n)` ` ` `b = b << 1;` ` ` `// Return the result` ` ` `return` `minimumOneBitOperations(` ` ` `(b >> 1) ^ b ^ n, res + b);` `}` `// Driver Code` `public` `static` `void` `Main()` `{` ` ` `// Given Input` ` ` `int` `N = 6;` ` ` `// Function call` ` ` `Console.Write(minimumOneBitOperations(N,0));` `}` `}` `// This code is contributed by SURENDRA_GANGWAR.` |

## Javascript

`<script>` ` ` `// Javascript program for the above approach` ` ` `// Function to find minimum` `// operations required to convert` `// N to 0` `function` `minimumOneBitOperations( n, res = 0)` `{` ` ` `// Base Case` ` ` `if` `(n == 0)` ` ` `return` `res;` ` ` ` ` `// Store the highest power of 2` ` ` `// less than or equal to n` ` ` `let b = 1;` ` ` `while` `((b << 1) <= n)` ` ` `b = b << 1;` ` ` ` ` `// Return the result` ` ` `return` `minimumOneBitOperations((b >> 1) ^ b ^ n, res + b);` `}` ` ` `// Driver Code` ` ` `// Given Input` ` ` `let N = 6;` ` ` ` ` `// Function call` ` ` `document.write(minimumOneBitOperations(N));` ` ` `// This code is contributed by` `// Potta Lokesh` ` ` ` ` `</script>` |

**Output:**

4

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