Минимални операции за конвертиране на X в Y


Ниво на трудност M
Често задавани в Амазонка FactSet Фанатиците Fourkites JP Morgan Myntra Samsung Spotify Площад
Широчина Първо търсене Крива

Декларация за проблема

Проблемът „Минимални операции за преобразуване на X в Y“ гласи, че са ви дадени две числа X и Y, необходимо е да конвертирате X в Y, като използвате следните операции:

Стартовият номер е X. Следват се операции върху X и върху числата, които се генерират като междинен резултат.

  1. умножете числото по 2.
  2. намалете броя с 1.

Открийте минималния брой стъпки, необходими за преобразуване на X в Y, като използвате операциите, споменати по-горе.

Ограничения: 0 <X, Y <1000

Пример

X = 3, Y = 11
3

Обяснение: 3 * 2 = 6, 6 * 2 = 12, 12-1 = 11 3 стъпки

X = 2, Y = 10
5

Обяснение: 2 * 2 = 4, 4-1 = 3, 3 * 2 = 6, 6-1 = 5, 5 * 2 = 10 -> 5 стъпки

Подход

Прилагаме a BFS базиран алгоритъм. Тогава можем да изпълним 2 операции или умножаваме по 2, или изваждаме по 1. По този начин можем да достигнем до всички числа, които могат да бъдат генерирани, като се използва началното число X и изпълняваме дадените две операции. Ако някакво генерирано число е равно на входно число Y, се получава. По този начин ние просто връщаме броя стъпки, предприети за генериране на числото Y. Докато генерираме числа, е важно да имаме предвид следните точки:

  1. Пренебрегваме вмъкването на номера в опашката на BFS, ако генерираното число не отговаря на ограниченията.
  2. Ако генерираният в момента номер вече е генериран преди. Ние просто игнорираме номера, като не го добавяме към опашката BFS. Хеш набор се използва за проследяване на числата, които са генерирани до момента.
  3. Проследяваме броя на операциите (в променлива с име ниво) изпълнява се за генериране на число от начален номер X чрез извършване на необходимите операции.

Алгоритъм за намиране на минимални операции за конвертиране на X в Y

  1. Създаване на опашка за обръщане на BFS и поставете началния номер X и той е на ниво в опашката. Нивото на началния номер е 0, тъй като броят на операциите, необходими за преобразуване на X в X, е 0.
  2. Създаване на HashSet който съхранява генерираните досега числа.
  3. След това започнете обхождането на BFS.
  4. Изкачете възел от опашката, ако стойността на възела е равна на входния номер Y. И ниво на връщане (Минимален брой операции от X) на този възел.
  5. В противен случай добавете този възел в нашия хеш набор (маркирайки го като посетен).
  6. Сега умножете изскачащата стойност на възел по 2 и проверете дали тя присъства в набора.
  7. Ако така генерираното число не присъства в комплекта. По този начин вмъкнете номера в опашката заедно с неговото ниво (ниво на този възел е генериран = ниво на изскачащ (родителски) възел + 1).
  8. Намалете изскачащата стойност на възела с 1 и проверете дали тя присъства в комплекта.
  9. Ако така генерираното число не присъства в комплекта. По този начин вмъкнете номера в опашката заедно с неговото ниво (ниво на този възел е генериран = ниво на изскачащ (родителски) възел + 1).
  10. Повторете итеративно стъпките 3-9, докато не срещнем условие за връщане в стъпка-4.

Алгоритъмът е изобразен по-долу:

Минимални операции за конвертиране на X в Y

код

C ++ код за намиране на минимални операции за конвертиране на X в Y

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

/* class definition to treat 
numbers generated as nodes */
class Node
{
    public:
    int num;
    int level;
    
    Node(int num,int level)
    {
        this->num = num;
        this->level = level;
    }
};

/* function to find minimum number of 
operations required to convert x into y */
int minOperation(int x,int y)
{
    queue<Node*> q;
    unordered_set <int> us;
    
    Node *node = new Node(x,0);
    q.push(node);
    
    while(!q.empty())
    {
        Node *top = q.front();
        q.pop();
        
        if(top->num == y)
        return top->level;
        
        us.insert(top->num);
        
        /* Multiplication Operation */
        if(us.find(2*top->num) == us.end())
        {
            Node *temp = new Node(2*top->num,top->level+1);
            q.push(temp);
        }
        
        /* Subtraction Operation */
        if(us.find(top->num-1) == us.end() && top->num-1 > 0)
        {
            Node *temp = new Node(top->num-1,top->level+1);
            q.push(temp);
        }
    }
}
/* Main function */
int main()
{
    int x = 2,y = 10;
    cout<<minOperation(x,y)<<endl;
    
    return 0;
}
5

Java код за намиране на минимални операции за конвертиране на X в Y

import java.util.*;
import java.io.*;

class TutorialCup 
{
    /* class definition to treat 
    numbers generated as nodes */
    static class Node
    {
        int num;
        int level;
        
        Node(int num,int level)
        {
            this.num = num;
            this.level = level;
        }
    }
    
    /* function to find minimum number of 
    operations required to convert x into y */
    static int minOperation(int x,int y)
    {
        Queue <Node> q = new LinkedList<>();
        HashSet <Integer> hs = new HashSet<Integer>();
        
        Node node = new Node(x,0);
        q.add(node);
        
        while(!q.isEmpty())
        {
            Node top = q.poll();
            
            if(top.num == y)
            return top.level;
            
            hs.add(top.num);
            
            /* Multiplication Operation */
            if(!hs.contains(2*top.num))
            {
                Node temp = new Node(2*top.num,top.level+1);
                q.add(temp);
            }
            
            /* Subtraction Operation */
            if(!hs.contains(top.num-1) && top.num-1 > 0)
            {
                Node temp = new Node(top.num-1,top.level+1);
                q.add(temp);
            }
        }
        
        return 0;
    }
    /* Main function */
  public static void main (String[] args) 
  {
      int x = 2,y = 10;
        System.out.println(minOperation(x,y));
  }
}
5

Анализ на сложността

Сложност във времето

Трудно е да се коментира сложността във времето за намиране на число, използвайки горния подход. Но все пак можем да коментираме най-лошата времева сложност. В най-лошия случай това, което може да се случи, е да преминем през всички числа, присъстващи под ограничението. Дори преминавайки през всички числа, ние не намираме необходимия ни номер. Така сложността на времето е НА), където N е възможно най-големият елемент при дадени ограничения.

Сложност на пространството

Трудно е да се коментира и космическата сложност. Но подобно на това, което направихме със сложността на времето. Така че същото важи и за сложността на космоса. В най-лошия случай ще вмъкнем всички елементи в опашката. Това кара алгоритъма да се вземе НА) пространство, където N е възможно най-големият брой при дадено ограничение.