Минимальные операции для преобразования X в Y


Сложный уровень средний
Часто спрашивают в Амазонка Набор фактов Фанатики Фуркиты 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 шагов

Подход

Мы применяем 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 - наибольшее число, возможное при заданном ограничении.