मित्र जोडीची समस्या


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन यामध्ये जीई हेल्थकेअर Google हनिवेल जेपी मॉर्गन
डायनॅमिक प्रोग्रामिंग मॉड्यूलर अंकगणित

समस्या विधान

“मित्र जोडण्यातील समस्या” असे सांगते की तेथे एन मित्र आहेत. आणि ते प्रत्येक अविवाहित राहू शकतात किंवा एकमेकांशी जोडी बनू शकतात. पण एकदा एखादी जोडी बनल्यानंतर ते दोन मित्र जोडीमध्ये भाग घेऊ शकत नाहीत. तर, मित्रांना जोडण्यासाठी किंवा ते अविवाहित राहू शकतील अशा एकूण मार्गांची आपल्याला शोधणे आवश्यक आहे

उदाहरण

3
4

मित्र जोडीची समस्या
मित्र जोडण्याच्या समस्येसाठी दृष्टिकोण

त्याऐवजी एक मोठी समस्या म्हणून विचार करण्याऐवजी. प्रथम छोट्या एन साठी सोडवण्याचा प्रयत्न करू. एन = 1 साठी, उत्तर 1 आहे. एन = 2 साठी उत्तर आहे. एकतर दोन्ही मित्र अविवाहित राहतात किंवा ते जोडतात. एन = 2 साठी एकतर तिसरा मित्र अविवाहित राहू शकतो. तर त्या उत्तराचे उत्तर एन = २ सह असले पाहिजे. कारण अशा सर्व प्रकरणांमध्ये आपला तिसरा मित्र अविवाहित राहू शकतो. आणि जोडीसाठी, तो मित्रांपैकी कोणाही एक निवडू शकतो. म्हणून एन -3 मित्रांमधील 2 मित्र निवडणे आणि नंतर इतर जोडीदार राहू शकतात / अविवाहित राहू शकतात असे मार्ग = (एन -1) * एफ (एन -1). आता आम्ही समस्येच्या रिकर्सीव्ह सूत्राचा विचार करू शकतो.

F(N)     =     F(N-1)   +   (N-1)*F(N-2)
                  ^              ^
                  |              |
Nth friend (stays single) (pairs with N-1 friends)

पासून रिकर्सिव फॉर्म्युलाआपण पाहु शकतो की एफ (एन) मोजताना आपण एफ (एन -2) ची गणना करतो. आणि मग एफ (एन -1) साठी देखील आम्ही एफ (एन -2) मोजू. व्हॅल्यू रीकंपूट करण्याऐवजी आपण वापरू डायनॅमिक प्रोग्रामिंग. येथे आपण 0 ते एन पर्यंतची संपूर्ण एफ (एन) व्हॅल्यूज संचित करू शकतो. परंतु ते आवश्यक नाही. F (N) चे मूल्य केवळ F (N-1) आणि F (N-2) वर अवलंबून आहे जे शेवटचे 2 मूल्ये आहे. तर आपण शेवटची 2 व्हॅल्यूज ठेवत आहोत. कारण यामुळे आपली जागा वाचू शकेल.

कोड

मित्र जोडण्याच्या समस्येसाठी सी ++ कोड

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

int main()
{
  // number of friends
  int n;cin>>n;

  int last = 2, lastTolast = 1;
  // here last denotes F(N-1) and lastTolast denotes F(N-2)
  // we can also use a dp array but that will only increase space complexity
  // and from the recursive formula we can see that
  // F(N) is dependent only on F(N-1) and F(N-2)
  int current;
  for(int i=3;i<=n;i++){
    current = last + (i-1)*lastTolast;
    lastTolast = last;
    last = current;
  }
  cout<<current<<endl;
}E
4
10

मित्र जोडण्याच्या समस्येसाठी जावा कोड

import java.util.*;

class Main{
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();// number of friends

    int last = 2, lastTolast = 1;
    // here last denotes F(N-1) and lastTolast denotes F(N-2)
    // we can also use a dp array but that will only increase space complexity
    // and from the recursive formula we can see that
    // F(N) is dependent only on F(N-1) and F(N-2)
    int current;
    for(int i=3;i<=n;i++){
      current = last + (i-1)*lastTolast;
      lastTolast = last;
      last = current;
    }
    System.out.println(current);
  }
}
4
10

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

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

ओ (एन), कारण ते शोधण्यासाठी एन पर्यंत पळवाट चालवावी लागेल. एफ (एन) एफ (एन -1) आणि एफ (एन -2) वर अवलंबून आहे.

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

ओ (1), आम्ही मोजण्यासाठी फक्त तीन व्हेरिएबल्स वापरली आणि त्यामुळे अंतर आवश्यक असते.