X मध्ये Y मध्ये रूपांतरित करण्यासाठी किमान ऑपरेशन्स


अडचण पातळी मध्यम
वारंवार विचारले ऍमेझॉन फॅक्टसेट कट्टरता फोरकाइट्स जेपी मॉर्गन Myntra सॅमसंग Spotify स्क्वेअर
रुंदी प्रथम शोध आलेख

समस्या विधान

“एक्स मध्ये Y मध्ये रूपांतरित करण्यासाठी किमान ऑपरेशन्स” ही समस्या नमूद करते की आपल्याला X आणि Y हे दोन क्रमांक दिले आहेत, पुढील क्रियांचा वापर करून X ला Y मध्ये रूपांतरित करणे आवश्यक आहे:

प्रारंभ क्रमांक X आहे. पुढील ऑपरेशन्स एक्स वर आणि दरम्यानच्या निकालाच्या रूपात व्युत्पन्न केलेल्या संख्येवर केल्या जाऊ शकतात.

  1. संख्या 2 ने गुणाकार करा.
  2. संख्या 1 ने कमी करा.

वर नमूद केलेल्या ऑपरेशन्सचा वापर करून एक्स मध्ये वाय मध्ये रूपांतरित करण्यासाठी आवश्यक किमान चरणांची संख्या शोधा.

प्रतिबंध: 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 ने गुणाकार करा किंवा 1 वजा करा. अशाप्रकारे आपण आरंभिक X चा वापर करून तयार केलेल्या सर्व संख्या पोहोचू आणि दिलेल्या दोन ऑपरेशन्स करू. कोणतीही व्युत्पन्न संख्या इनपुट क्रमांकाइतकी असल्यास वाय प्राप्त केली जाते. अशा प्रकारे आम्ही वाय क्रमांक काढण्यासाठी घेतलेल्या चरणांची संख्या फक्त परत करतो. संख्या निर्माण करताना खालील बाबी लक्षात ठेवणे आवश्यक आहेः

  1. व्युत्पन्न केलेली संख्या मर्यादा पूर्ण करीत नसल्यास आम्ही संख्या बीएफएस रांगेत घालण्याकडे दुर्लक्ष करतो.
  2. जर सध्या व्युत्पन्न केलेला नंबर आधीपासून व्युत्पन्न केला गेला असेल तर. आम्ही फक्त बीएफएस रांगेत न जोडून नंबरकडे दुर्लक्ष करतो. आतापर्यंत व्युत्पन्न केलेल्या नंबरचा मागोवा ठेवण्यासाठी हॅश सेटचा वापर केला जातो.
  3. आम्ही ऑपरेशन्सच्या संख्येचा मागोवा ठेवतो (नावाच्या चलनात) पातळी) आवश्यक ऑपरेशन्स करून आरंभ क्रमांकापासून नंबर तयार करण्यासाठी प्रदर्शन केले.

X मध्ये Y मध्ये रूपांतरित करण्यासाठी किमान ऑपरेशन्स शोधण्यासाठी अल्गोरिदम

  1. तयार शेपूट बीएफएस ट्रॅव्हर्सलसाठी आणि आरंभ क्रमांक एक्स घाला आणि तो स्तंभ रांगेत आहे. एक्स मध्ये रूपांतरित करण्यासाठी आवश्यक क्रियांची संख्या म्हणून 0 प्रारंभ होणारी संख्या 0 आहे.
  2. तयार हॅशसेट आतापर्यंत व्युत्पन्न केलेली संख्या संचयित करते.
  3. मग बीएफएस ट्रॅव्हर्सल सुरू करा.
  4. नोडचे मूल्य इनपुट नंबर वाय बरोबर असल्यास रांगेवरून नोड पॉप करा. आणि या नोडच्या रिटर्न लेव्हल (एक्समधून ऑपरेशन्सची किमान संख्या) असेल तर.
  5. नाहीतर हा नोड आमच्या हॅश सेटमध्ये जोडा (भेट दिल्याप्रमाणे चिन्हांकित करा).
  6. आता पॉपड नोड व्हॅल्यू 2 ने गुणाकार करा आणि ते सेटमध्ये उपलब्ध आहे का ते तपासा.
  7. जर अशी व्युत्पन्न केलेली संख्या सेटमध्ये नसेल तर. अशा प्रकारे त्याच्या स्तरासह रांगेत संख्या घाला (या नोडचे व्युत्पन्न स्तर = पॉपड (पालक) नोड +1 चे स्तर).
  8. पॉपड नोड मूल्य 1 ने कमी करा आणि ते सेटमध्ये उपलब्ध आहे का ते तपासा.
  9. जर अशी व्युत्पन्न केलेली संख्या सेटमध्ये नसेल तर. अशा प्रकारे त्याच्या स्तरासह रांगेत संख्या घाला (या नोडचे व्युत्पन्न स्तर = पॉपड (पालक) नोड +1 चे स्तर).
  10. आमच्याकडे परत स्थितीत येईपर्यंत 3-9 चरणांचे पुनरावृत्ती करा चरण -4.

अल्गोरिदम खाली चित्रित केले आहे:

X मध्ये Y मध्ये रूपांतरित करण्यासाठी किमान ऑपरेशन्स

कोड

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

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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

वरील पध्दतीचा वापर करुन संख्या शोधण्यासाठी वेळेच्या जटिलतेबद्दल भाष्य करणे कठिण आहे. परंतु आम्ही अजूनही सर्वात वाईट वेळेच्या जटिलतेवर टिप्पणी देऊ शकतो. सर्वात वाईट परिस्थितीत आपण सर्व मर्यादेच्या मर्यादेखाली जाऊ शकतो. जरी सर्व क्रमांकावरुन जात असतानाही आम्हाला आमची आवश्यक संख्या सापडत नाही. अशा प्रकारे वेळ गुंतागुंत आहे ओ (एन), जेथे दिलेल्या मर्यादा अंतर्गत एन सर्वात मोठा घटक आहे.

स्पेस कॉम्प्लेक्सिटी

अंतराळ जटिलतेवर भाष्य करणे देखील अवघड आहे. परंतु वेळेच्या जटिलतेसह आम्ही जे केले त्यासारखेच. स्पेस कॉम्प्लेक्ससाठीही हेच खरे आहे. सर्वात वाईट परिस्थितीत आम्ही सर्व घटक रांगेत समाविष्ट करीत आहोत. हे घेणे अल्गोरिदम करते ओ (एन) जागा, जेथे दिलेल्या मर्यादा अंतर्गत एन ही सर्वात मोठी संख्या आहे.