الحد الأدنى من العمليات لتحويل X إلى Y.


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون مجموعة الحقائق المتعصبون فوركايتس JP مورغان Myntra سامسونج سبوتيفي مربع
اتساع البحث الأول رسم بياني

المشكلة بيان

تنص مشكلة "الحد الأدنى من العمليات لتحويل X إلى Y" على أنه تم إعطاؤك رقمين X و Y ، ومن الضروري تحويل X إلى Y باستخدام العمليات التالية:

رقم البداية هو X. يمكن إجراء العمليات التالية على X وعلى الأرقام التي تم إنشاؤها كنتيجة وسيطة.

  1. اضرب الرقم في 2.
  2. إنقاص الرقم بمقدار 1.

تعرف على الحد الأدنى من الخطوات المطلوبة لتحويل X إلى Y باستخدام العمليات المذكورة أعلاه.

قيود: 0 <س ، ص> 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. وبهذه الطريقة يمكننا الوصول إلى جميع الأرقام التي يمكن إنشاؤها باستخدام رقم البداية X وتنفيذ العمليتين المحددتين. إذا كان أي رقم تم إنشاؤه يساوي إدخال رقم يتم الحصول عليه. وبالتالي نعيد ببساطة عدد الخطوات التي تم اتخاذها لإنشاء الرقم 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 هو أكبر عدد ممكن في ظل قيد معين.