Xти Yге айлантуучу минималдуу операциялар


Кыйынчылык деңгээли орто
Көп суралган Amazon 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

Explanation: 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ге айландыруу үчүн талап кылынган операциялардын саны 0 болот.
  2. түзүү HashSet ушул кезге чейин түзүлгөн сандарды сактайт.
  3. Андан кийин BFS өтүү башталат.
  4. Кезектеги түйүндү чыгарыңыз, эгерде түйүн мааниси Y киргизүү номерине барабар болсо жана бул түйүндүн кайтарым деңгээли (Х-дан минималдуу операциялардын саны).
  5. Башка, бул түйүндү биздин таштанды топтомубузга кошуңуз (аны барганыңыз катары белгилеңиз).
  6. Эми, ачылган түйүндүн маанисин 2ге көбөйтүп, анын топтомдо бар экендигин текшериңиз.
  7. Эгерде ушунча түзүлгөн сан топтомдо жок болсо. Ошентип, санды кезекке анын деңгээли менен кошо киргизиңиз (бул түйүндүн деңгээли = ташталган (ата-эне) түйүнүнүн деңгээли + 1).
  8. Түзүлгөн түйүндүн маанисин 1ге төмөндөтүп, анын топтомдо бар экендигин текшериңиз.
  9. Эгерде ушунча түзүлгөн сан топтомдо жок болсо. Ошентип, санды кезекке анын деңгээли менен кошо киргизиңиз (бул түйүндүн деңгээли = ташталган (ата-эне) түйүнүнүн деңгээли + 1).
  10. Кайтаруу шартына туш келгенге чейин 3-9 кадамдарды кайталап кайталаңыз 4-кадам.

Алгоритм төмөндө чагылдырылган:

Xти Yге айлантуучу минималдуу операциялар

коду

Xти Yге которуу үчүн минималдуу операцияларды табуу үчүн C ++ коду

#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

X кодун Y түрүнө которуу үчүн минималдуу операцияларды табуу үчүн Java коду

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

Комплекстик анализ

Убакыт татаалдыгы

Жогорудагы ыкманы колдонуп, номур табуунун татаалдыгы жөнүндө комментарий берүү кыйын. Бирок, биз эң начар убакыттын татаалдыгы жөнүндө дагы деле айта алабыз. Эң начар болгон учурда, биз чектөө астында турган бардык сандардан өтүп жатабыз. Бардык сандарды карап чыгып деле, керектүү номерибизди таппай жатабыз. Ошентип, убакыттын татаалдыгы O (N), бул жерде N - берилген чектөөлөр боюнча мүмкүн болгон эң чоң элемент.

Космостун татаалдыгы

Космостун татаалдыгы жөнүндө да комментарий берүү кыйын. Бирок биз убакыттын татаалдыгы менен жасаган нерсеге окшош. Ошентип, космостогу татаалдык үчүн дагы ушундай. Жаман абалда, биз бардык элементтерди кезекке киргизебиз. Бул алгоритмди кабыл алат O (N) мейкиндик, бул жерде N - берилген чектөө боюнча мүмкүн болгон эң чоң сан.