Minimize moves to reduce N to 0 using given operations
Given a number N, and some operations that can be performed, the task is to find the minimum number of moves to convert N to 0. In one move operation, one of the following can be performed:
- Increment or decrement the value of N by 1.
- Multiply the value of N by -1.
- Divide the value of N by 2 if N is even.
- Reduce the value of N to √N if N is a perfect square.
Example:
Input: N = 50
Output: 6
Explanation: The moves performed are: 50 (/2) -> 25 (√) -> 5 (- 1) -> 4 (/2) -> 2 (-1) -> 1 (-1) -> 0. Therefore, the required number of moves is 6 which is the minimum possible.Input: N = 75
Output: 8
Approach: The given problem can be solved efficiently by using dynamic programming. The idea is to use hashing and breadth-first search on 0 till N is reached. Hashing is used so that the same number is not visited twice. The below steps can be followed to solve the problem:
- Use BFS by adding all the possible numbers that can be reached from 0 into a queue and also in a hashmap so that they are not visited again
- Return the number of moves calculated after reaching N.
Below is the implementation of the above approach:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; class Node { public : int val, moves; // Constructor Node( int v, int m) { val = v; moves = m; } }; // Function to calculate // minimum number of moves // required to convert N to 0 int minMoves( int N) { // Initialize a hashset // to mark the visited numbers set< int > set; // Initialize a queue queue<Node*> q ; // Mark 0 as visited set.insert(0); // Add 0 into the queue q.push( new Node(0, 0)); // while N is not reached while (!q.empty()) { // poll out current node Node *curr = q.front(); q.pop(); // If N is reached if (curr->val == N) { // Return the number of moves used return curr->moves; } if (set.find(curr->val - 1)==set.end()) { // Mark the number as visited set.insert(curr->val - 1); // Add the number in the queue q.push( new Node(curr->val - 1, curr->moves + 1)); } if (set.find(curr->val + 1)==set.end()) { // Mark the number as visited set.insert(curr->val + 1); // Add the number in the queue q.push( new Node(curr->val + 1, curr->moves + 1)); } if (set.find(curr->val * 2)==set.end()) { // Mark the number as visited set.insert(curr->val * 2); // Add the number in the queue q.push( new Node(curr->val * 2, curr->moves + 1)); } int sqr = curr->val * curr->val; if (set.find(sqr)==set.end()) { // Mark the number as visited set.insert(sqr); // Add the number in the queue q.push( new Node(sqr, curr->moves + 1)); } if (set.find(-curr->val)==set.end()) { // Mark the number as visited set.insert(-curr->val); // Add the number in the queue q.push( new Node(-curr->val, curr->moves + 1)); } } return -1; } // Driver code int main() { int N = 50; // Call the function // and print the answer cout<<(minMoves(N)); } // This code is contributed by Potta Lokesh |
Java
// Java implementation for the above approach import java.io.*; import java.util.*; class GFG { static class Node { int val, moves; // Constructor public Node( int val, int moves) { this .val = val; this .moves = moves; } } // Function to calculate // minimum number of moves // required to convert N to 0 public static int minMoves( int N) { // Initialize a hashset // to mark the visited numbers Set<Integer> set = new HashSet<>(); // Initialize a queue Queue<Node> q = new LinkedList<>(); // Mark 0 as visited set.add( 0 ); // Add 0 into the queue q.add( new Node( 0 , 0 )); // while N is not reached while (!q.isEmpty()) { // poll out current node Node curr = q.poll(); // If N is reached if (curr.val == N) { // Return the number of moves used return curr.moves; } if (!set.contains(curr.val - 1 )) { // Mark the number as visited set.add(curr.val - 1 ); // Add the number in the queue q.add( new Node(curr.val - 1 , curr.moves + 1 )); } if (!set.contains(curr.val + 1 )) { // Mark the number as visited set.add(curr.val + 1 ); // Add the number in the queue q.add( new Node(curr.val + 1 , curr.moves + 1 )); } if (!set.contains(curr.val * 2 )) { // Mark the number as visited set.add(curr.val * 2 ); // Add the number in the queue q.add( new Node(curr.val * 2 , curr.moves + 1 )); } int sqr = curr.val * curr.val; if (!set.contains(sqr)) { // Mark the number as visited set.add(sqr); // Add the number in the queue q.add( new Node(sqr, curr.moves + 1 )); } if (!set.contains(-curr.val)) { // Mark the number as visited set.add(-curr.val); // Add the number in the queue q.add( new Node(-curr.val, curr.moves + 1 )); } } return - 1 ; } // Driver code public static void main(String[] args) { int N = 50 ; // Call the function // and print the answer System.out.println(minMoves(N)); } } |
Python3
# Python code for the above approach from queue import Queue class Node: # Constructor def __init__( self , v, m): self .val = v self .moves = m # Function to calculate # minimum number of moves # required to convert N to 0 def minMoves(N): # Initialize a hashset # to mark the visited numbers _set = set () # Initialize a queue q = Queue() # Mark 0 as visited _set.add( 0 ) # Add 0 into the queue q.put(Node( 0 , 0 )) # while N is not reached while (q.qsize): # poll out current node curr = q.queue[ 0 ] q.get() # If N is reached if (curr.val = = N): # Return the number of moves used return curr.moves if ( not (curr.val - 1 ) in _set): # Mark the number as visited _set.add(curr.val - 1 ) # Add the number in the queue q.put(Node(curr.val - 1 , curr.moves + 1 )) if ( not (curr.val + 1 ) in _set): # Mark the number as visited _set.add(curr.val + 1 ) # Add the number in the queue q.put(Node(curr.val + 1 , curr.moves + 1 )) if ( not (curr.val * 2 ) in _set): # Mark the number as visited _set.add(curr.val * 2 ) # Add the number in the queue q.put(Node(curr.val * 2 , curr.moves + 1 )) sqr = curr.val * curr.val if ( not sqr in _set): # Mark the number as visited _set.add(sqr) # Add the number in the queue q.put(Node(sqr, curr.moves + 1 )) if ( not ( - curr.val) in _set): # Mark the number as visited _set.add( - curr.val) # Add the number in the queue q.put(Node( - curr.val, curr.moves + 1 )) return - 1 # Driver code N = 50 # Call the function # and print the answer print ((minMoves(N))) # This code is contributed by gfgking |
Javascript
<script> // Javascript code for the above approach class Node { // Constructor constructor(v, m) { this .val = v; this .moves = m; } }; // Function to calculate // minimum number of moves // required to convert N to 0 function minMoves(N) { // Initialize a hashset // to mark the visited numbers let set = new Set(); // Initialize a queue let q = []; // Mark 0 as visited set.add(0); // Add 0 into the queue q.unshift( new Node(0, 0)); // while N is not reached while (q.length) { // poll out current node let curr = q[q.length - 1]; q.pop(); // If N is reached if (curr.val == N) { // Return the number of moves used return curr.moves; } if (!set.has(curr.val - 1)) { // Mark the number as visited set.add(curr.val - 1); // Add the number in the queue q.unshift( new Node(curr.val - 1, curr.moves + 1)); } if (!set.has(curr.val + 1)) { // Mark the number as visited set.add(curr.val + 1); // Add the number in the queue q.unshift( new Node(curr.val + 1, curr.moves + 1)); } if (!set.has(curr.val * 2)) { // Mark the number as visited set.add(curr.val * 2); // Add the number in the queue q.unshift( new Node(curr.val * 2, curr.moves + 1)); } let sqr = curr.val * curr.val; if (!set.has(sqr)) { // Mark the number as visited set.add(sqr); // Add the number in the queue q.unshift( new Node(sqr, curr.moves + 1)); } if (!set.has(-curr.val)) { // Mark the number as visited set.add(-curr.val); // Add the number in the queue q.unshift( new Node(-curr.val, curr.moves + 1)); } } return -1; } // Driver code let N = 50; // Call the function // and print the answer document.write((minMoves(N))); // This code is contributed by gfgking </script> |
C#
using System; using System.Collections.Generic; class Node { public int val; public int moves; // Constructor public Node( int v, int m) { val = v; moves = m; } } class Program { // Function to calculate // minimum number of moves // required to convert N to 0 static int MinMoves( int N) { // Initialize a hashset // to mark the visited numbers HashSet< int > set = new HashSet< int >(); // Initialize a queue Queue<Node> q = new Queue<Node>(); // Mark 0 as visited set .Add(0); // Add 0 into the queue q.Enqueue( new Node(0, 0)); // while N is not reached while (q.Count > 0) { // poll out current node Node curr = q.Dequeue(); // If N is reached if (curr.val == N) { // Return the number of moves used return curr.moves; } if (! set .Contains(curr.val - 1)) { // Mark the number as visited set .Add(curr.val - 1); // Add the number in the queue q.Enqueue( new Node(curr.val - 1, curr.moves + 1)); } if (! set .Contains(curr.val + 1)) { // Mark the number as visited set .Add(curr.val + 1); // Add the number in the queue q.Enqueue( new Node(curr.val + 1, curr.moves + 1)); } if (! set .Contains(curr.val * 2)) { // Mark the number as visited set .Add(curr.val * 2); // Add the number in the queue q.Enqueue( new Node(curr.val * 2, curr.moves + 1)); } int sqr = curr.val * curr.val; if (! set .Contains(sqr)) { // Mark the number as visited set .Add(sqr); // Add the number in the queue q.Enqueue( new Node(sqr, curr.moves + 1)); } if (! set .Contains(-curr.val)) { // Mark the number as visited set .Add(-curr.val); // Add the number in the queue q.Enqueue( new Node(-curr.val, curr.moves + 1)); } } return -1; } static void Main( string [] args) { int N = 50; // Call the function // and print the answer Console.WriteLine(MinMoves(N)); } } |
6
Time Complexity: O(log N)
Auxiliary Space: O(K*log N), where K is the possible operations allowed