# Minimize steps to change N to power of 2 by deleting or appending any digit

Given an integer **N**, the task is to find the minimum number of steps required to change the number **N** to a perfect power of **2** using the following steps:

- Delete any one digit
**d**from the number. - Add any digit
**d**at the end of the number**N**.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

Input:N = 1092Output:2Explanation:

Following are the steps followed:

- Removing digit 9 from the number N(= 1092) modifies it to 102.
- Adding digit 4 to the end of number N(= 102) modifies it to 1024.
After the above operations, the number N is converted into perfect power of 2 and the number of moves required is 2, which is the minimum. Therefore, print 2.

Input:N = 4444Output:3

**Approach:** The given problem can be solved using the Greedy Approach, the idea is to store all the numbers that are the power of 2 and are less than **10 ^{20} **and check with each number the minimum steps to convert the given number into a power of

**2.**Follow the steps below to solve the problem:

- Initialize an array and store all the numbers that are the power of
**2**and less than**10**.^{20} - Initialize the answer variable
**best**as**length + 1**as the maximum number of steps needed. - Iterate over the range
**[0, len)**where**len**is the length of the array using the variable**x**and perform the following steps:- Initialize the variable, say
**position**as**0**. - Iterate over the range
**[0, len)**where**len**is the length of the number using the variable**i**and if the**position**is less than**len(x)**and**x[position]**is equal to**num[i]**, then increase the value of a**position**by**1**. - Update the value of
**best**as the minimum of**best**or**len(x) + len(num) – 2*position**.

- Initialize the variable, say
- After performing the above steps, print the value of
**best**as the result.

Below is the implementation of the above approach:

## Python3

`# Python program for the above approach` ` ` `# Function to find the minimum number of` `# steps required to reduce N to perfect` `# power of 2 by performing given steps` `def` `findMinimumSteps(N):` ` ` ` ` `num ` `=` `str` `(N)` ` ` `c ` `=` `1` ` ` `a ` `=` `[]` ` ` ` ` `# Stores all the perfect power of 2` ` ` `while` `True` `:` ` ` `if` `(c > ` `10` `*` `*` `20` `):` ` ` `break` ` ` `a.append(` `str` `(c))` ` ` `c ` `=` `c ` `*` `2` ` ` ` ` `# Maximum number of steps required` ` ` `best ` `=` `len` `(num) ` `+` `1` ` ` ` ` `# Iterate for each perfect power of 2` ` ` `for` `x ` `in` `a:` ` ` `position ` `=` `0` ` ` ` ` `# Comparing with all numbers` ` ` `for` `i ` `in` `range` `(` `len` `(num)):` ` ` ` ` `if` `position < ` `len` `(x) ` `and` `x[position] ` `=` `=` `num[i]:` ` ` `position ` `+` `=` `1` ` ` ` ` `# Update the minimum number of` ` ` `# steps required` ` ` `best ` `=` `min` `(best, ` `len` `(x) ` `+` `len` `(num) ` `-` `2` `*` `position)` ` ` ` ` `# Print the result` ` ` `print` `(best)` ` ` `# Driver Code` `N ` `=` `1092` ` ` `# Function Call` `findMinimumSteps(N)` |

**Output:**

2

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