ఫ్రెండ్స్ పెయిరింగ్ సమస్య


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్ Expedia ద్వారా GE హెల్త్ గూగుల్ హనీవెల్ జెపి మోర్గాన్
డైనమిక్ ప్రోగ్రామింగ్ మాడ్యులర్ అంకగణితం

సమస్యల నివేదిక

N స్నేహితులు ఉన్నారని “ఫ్రెండ్స్ పెయిరింగ్ ప్రాబ్లమ్” పేర్కొంది. మరియు ప్రతి ఒక్కటి ఒంటరిగా ఉండవచ్చు లేదా ఒకదానితో ఒకటి జత చేయవచ్చు. కానీ ఒక జత చేసిన తర్వాత, ఆ ఇద్దరు స్నేహితులు జతచేయడంలో పాల్గొనలేరు. కాబట్టి, స్నేహితులను జత చేయగల మొత్తం మార్గాల సంఖ్యను మీరు కనుగొనాలి లేదా వారు ఒంటరిగా ఉంటారు

ఉదాహరణ

3
4

ఫ్రెండ్స్ పెయిరింగ్ సమస్య
స్నేహితుల పెయిరింగ్ సమస్య కోసం అప్రోచ్

దాని గురించి పెద్ద సమస్యగా ఆలోచించే బదులు. మొదట చిన్న N కోసం పరిష్కరించడానికి ప్రయత్నిద్దాం. N = 1 కొరకు, సమాధానం 1. N = 2 కొరకు, సమాధానం 2. గాని స్నేహితులు ఇద్దరూ ఒంటరిగా ఉంటారు లేదా వారు జత చేస్తారు. N = 3 కోసం, మూడవ స్నేహితుడు ఒంటరిగా ఉండగలడు. కాబట్టి ఆ సమాధానం N = 2 తో ఉన్న సమస్యకు సమాధానంగా ఉండాలి. ఆ అన్ని సందర్భాల్లో మా మూడవ స్నేహితుడు ఒంటరిగా ఉండగలడు. మరియు జత చేయడానికి, ఇది స్నేహితుల్లో ఎవరినైనా ఎంచుకోవచ్చు. కాబట్టి N-1 స్నేహితుల నుండి 1 స్నేహితుడిని ఎన్నుకోవడం, ఆపై ఇతరులు జత / ఒంటరిగా ఉండటానికి అనేక మార్గాలు = (N-1) * F (N-2). ఇప్పుడు, సమస్య యొక్క పునరావృత సూత్రం గురించి మనం ఆలోచించవచ్చు.

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

నుండి పునరావృత సూత్రం, F (N) ను కంప్యూట్ చేసేటప్పుడు మనం F (N-2) ను లెక్కిస్తాము. ఆపై F (N-1) కొరకు, మేము F (N-2) ను లెక్కిస్తాము. కాబట్టి విలువలను తిరిగి కంప్యూట్ చేయడానికి బదులుగా, మనం ఉపయోగించాలి డైనమిక్ ప్రోగ్రామింగ్. ఇక్కడ, మేము మొత్తం F (N) విలువలను 0 నుండి N వరకు నిల్వ చేయవచ్చు. కాని అది అవసరం లేదు. 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

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై), ఎందుకంటే దానిని కనుగొనడానికి N వరకు లూప్‌ను అమలు చేయాలి. F (N) F (N-1) మరియు F (N-2) పై ఆధారపడి ఉంటుంది కాబట్టి.

అంతరిక్ష సంక్లిష్టత

ఓ (1), మేము గణన కోసం మూడు వేరియబుల్స్ మాత్రమే ఉపయోగించాము మరియు అందువల్ల అవసరమైన అంతరం స్థిరంగా ఉంటుంది.