ద్విపద గుణకం


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది డైరెక్టి Expedia ద్వారా HackerRank Xome
డైనమిక్ ప్రోగ్రామింగ్ లీట్‌కోడ్ మఠం

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

ఇచ్చిన విలువ n మరియు k కోసం ద్విపద గుణకాన్ని కనుగొనండి.

"లో గణితద్విపద గుణకాలు సానుకూలంగా ఉన్నాయి పూర్ణాంకాల సంభవిస్తుంది గుణకాలు లో ద్విపద సిద్ధాంతం. సాధారణంగా, ద్విపద గుణకం ఒక జత పూర్ణాంకాలచే సూచించబడుతుంది n ≥ k ≥ 0 మరియు ఇలా వ్రాయబడింది ”- నుండి కోట్ చేయబడింది వికీపీడియా.

ఉదాహరణ

n = 5, k = 2
10

వివరణ: ద్విపద గుణకం లెక్కించడానికి సూత్రాన్ని ఉపయోగించి, మేము కనుగొన్నాము 5 సి 3 ఇది 10 కి సమానం.

ద్విపద గుణకం అంటే ఏమిటి?

ద్విపద గుణకాన్ని ఎలా కనుగొనాలో తెలుసుకునే ముందు. క్లుప్తంగా చర్చిద్దాం ద్విపద గుణకం అంటే ఏమిటి? మరియు అది ఎందుకు అవసరం?

ఎందుకంటే కాంబినేటరిక్స్ సమస్యలను పరిష్కరించడానికి ద్విపద గుణకం ఎక్కువగా ఉపయోగించబడుతుంది. మీకు కొన్ని ఉన్నాయని చెప్పండి విభిన్న అంశాలు మరియు మీరు ఎంచుకోవాలి అంశాలు. కాబట్టి, మీరు ఈ సమస్యను పరిష్కరించాలనుకుంటే, n మూలకాల నుండి k మూలకాలను ఎన్నుకునే అన్ని కేసులను సులభంగా వ్రాయవచ్చు. N పెరిగినప్పుడు ఇది చాలా సమయం తీసుకునే ప్రక్రియ. ద్విపద గుణకం ఉపయోగించి ఈ సమస్యను సులభంగా పరిష్కరించవచ్చు. అంతకన్నా ఎక్కువ, n విభిన్న మూలకాల నుండి k మూలకాలను ఎన్నుకునే ఈ సమస్య ద్విపద గుణకాన్ని నిర్వచించే మార్గం n సి క. ఇచ్చిన సూత్రాన్ని ఉపయోగించి ద్విపద గుణకాన్ని సులభంగా లెక్కించవచ్చు:

ఇప్పుడు మేము బేసిక్స్‌లో మంచివాళ్ళం కాబట్టి, దీన్ని సమర్థవంతంగా లెక్కించడానికి మార్గాలను కనుగొనాలి.

ద్విపద గుణకాన్ని కనుగొనటానికి అమాయక విధానం

ఈ విధానం కాదు చాలా అమాయక. 3 మూలకాలలో 5 అంశాలను ఎన్నుకునే మార్గాల సంఖ్యను కనుగొనమని మిమ్మల్ని అడిగినట్లు పరిగణించండి. కాబట్టి మీరు సులభంగా కనుగొనవచ్చు n!, క! మరియు (nk)! మరియు ఇచ్చిన సూత్రంలో విలువలను ఉంచండి. ఈ పరిష్కారం మాత్రమే పడుతుంది సరైన సమయానికి మరియు O (1) స్థలం. కానీ కొన్నిసార్లు మీ కారకమైన విలువలు పొంగిపోవచ్చు కాబట్టి మేము దానిని జాగ్రత్తగా చూసుకోవాలి. మేము ఒకే ద్విపద గుణకాన్ని లెక్కించాలనుకుంటే ఈ విధానం మంచిది. కానీ చాలా సార్లు మనం చాలా ద్విపద గుణకాలను లెక్కించాలి. కాబట్టి, వాటిని ముందే కంప్యూట్ చేయడం మంచిది. ద్విపద గుణకాలను సమర్థవంతంగా ఎలా కనుగొనాలో మేము కనుగొంటాము.

ద్విపద గుణకాన్ని కనుగొనడానికి ఆప్టిమైజ్ చేసిన విధానం

ఒకే ద్విపద గుణకాన్ని కనుగొనాలనుకుంటే, అమాయక విధానం అమాయకత్వం కాదు. కానీ మనం చాలా ద్విపద గుణకాలను కనుగొనవలసి వచ్చినప్పుడు. కాబట్టి సమస్య సమయ పరిమితిలో పూర్తి చేయడం కష్టం అవుతుంది. ఎందుకంటే అమాయక విధానం ఇంకా సమయం తీసుకుంటుంది. కాబట్టి, ఇక్కడ మనకు కొన్ని ప్రశ్నలు ఉన్నాయి, అక్కడ మనం లెక్కించమని అడిగారు nCk ఇచ్చిన n మరియు k కొరకు. చాలా ప్రశ్నలు ఉండవచ్చు. దీనిని పరిష్కరించడానికి మనకు పాస్కల్ యొక్క త్రిభుజం గురించి తెలిసి ఉండాలి. మనం ఏమి చేయబోతున్నామో ఎందుకు చేయబోతున్నామో మాకు స్పష్టంగా అర్థమయ్యే కారణం.

ద్విపద గుణకం

పాస్కల్ త్రిభుజంలోని ఏదైనా కణం ద్విపద గుణకాలను సూచిస్తుంది. పాస్కల్ యొక్క త్రిభుజానికి సంబంధించి మనం కొన్ని విషయాలు తెలుసుకోవాలి.

  1. ఇది 0 వ వరుసతో మొదలవుతుంది.
  2. పాస్కల్ యొక్క త్రిభుజంలోని ఏదైనా సంఖ్య ద్విపద గుణకాన్ని సూచిస్తుంది.
  3. అడ్డు వరుస యొక్క సరిహద్దుల్లో లేని ఏదైనా ద్విపద గుణకం ఎడమ మరియు కుడి దిశలో దాని పైన ఉన్న మూలకాల సమ్మషన్ నుండి తయారవుతుంది.

inte \ బినోమ్ {n} {k}} = {in బినోమ్ {n-1} {k-1}} + {\ బినోమ్ {n-1} {k}} ad క్వాడ్ {\ టెక్స్ట్ all అన్ని పూర్ణాంకాలకు}} n , k: 1 \ leq k \ leq n-1,

ప్రతి ద్విపద గుణకం రెండు ద్విపద గుణకాలపై ఆధారపడి ఉంటుందని ఇప్పుడు మనకు తెలుసు. కాబట్టి మనం వాటిని ఎలాగైనా పరిష్కరించగలిగితే, మనకు అవసరమైన ద్విపద గుణకాన్ని కనుగొనడానికి వాటి మొత్తాన్ని సులభంగా తీసుకోవచ్చు. కాబట్టి ఇది మనకు ఉపయోగించుకునే అంతర్ దృష్టిని ఇస్తుంది డైనమిక్ ప్రోగ్రామింగ్. ఇక్కడ బేస్‌కేసులు కూడా చాలా తేలికగా పేర్కొనబడతాయి dp [0] [0] = 1, dp [i] [0] = dp [i] [[i] = 1.

కోడ్

ద్విపద గుణకాన్ని కనుగొనడానికి సి ++ కోడ్

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

int C[51][51];

// this function just makes our pascal triangle
void precomputeBinomialCoefficients()
{

  for (int i = 0; i <= 50; i++)
  {
    for (int j = 0; j <= i; j++)
    {
      // Base Cases
      if (j == 0 || j == i)
        C[i][j] = 1;
      else
        C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; // use recursive formula
    }
  }
}

int main()
{
  // precomputationis being done for n = 50, you can change the value of n
  precomputeBinomialCoefficients();
  int noOfQueries;cin>>noOfQueries;
  while(noOfQueries--){
    // here n & k do not satisfy the propertoes of binomial coefficient
    // then we will answer it as 0
    int n,k;cin>>n>>k;
    if(n<=50 && k<=50)
      cout<<C[n][k]<<endl;
    else
      cout<<0<<endl;
  }
}
3
5 3
5 2
6 4
10
10
15

ద్విపద గుణకాన్ని కనుగొనడానికి జావా కోడ్

import java.util.*;

class Main{
  static int C[][];

  // this function just makes our pascal triangle
  static void precomputeBinomialCoefficients() 
  {
    for (int i = 0; i <= 50; i++) 
    { 
      for (int j = 0; j <= i; j++) 
      { 
        // Base Cases 
        if (j == 0 || j == i) 
          C[i][j] = 1; 
        else
          C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; // use recursive formula
      } 
    }	
  } 

  public static void main(String[] args)
  {
    C = new int[51][51];
    // precomputationis being done for n = 50, you can change the value of n
    precomputeBinomialCoefficients();
    Scanner sc = new Scanner(System.in);
    int noOfQueries;
    noOfQueries = sc.nextInt();
    while(noOfQueries-- > 0){
      // here n & k do not satisfy the propertoes of binomial coefficient
      // then we will answer it as 0
      int n = sc.nextInt();
      int k = sc.nextInt();
      if(n<=50 && k<=50)
        System.out.println(C[n][k]);		
      else
        System.out.println(0);
    }
  }
}
3
5 2
5 3
6 3
10
10
15

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

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

O (N ^ 2 + Q),  ఎందుకంటే మేము ద్విపద గుణకాలను nCn వరకు ముందే కంప్యూట్ చేస్తున్నాము. ఈ ఆపరేషన్ ప్రతి ప్రశ్నకు సమాధానం ఇవ్వడానికి O (N ^ 2) సమయం మరియు O (1) సమయం పడుతుంది.

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

O (N ^ 2),  ద్విపద గుణకాల యొక్క ముందస్తు కంప్యూటెడ్ ఫలితాలను నిల్వ చేయడానికి.