NCr% p ಅನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಿ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಸೆಂಚರ್ ಕ್ಯಾಡೆನ್ಸ್ ಇಂಡಿಯಾ ಕೊಮ್ಲಿ ಮೀಡಿಯಾ ಓಲಾ ಕ್ಯಾಬ್ಸ್ ಸ್ಕ್ವೇರ್
ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್ ಮಠ

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

“ಕಂಪ್ಯೂಟ್ nCr% p” ಸಮಸ್ಯೆ ನೀವು ದ್ವಿಪದ ಗುಣಾಂಕ ಮಾಡ್ಯುಲೋ p ಅನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು ಎಂದು ಹೇಳುತ್ತದೆ. ಆದ್ದರಿಂದ ನೀವು ಮೊದಲು ದ್ವಿಪದ ಗುಣಾಂಕದ ಬಗ್ಗೆ ತಿಳಿದಿರಬೇಕು. ನಾವು ಅದನ್ನು ಹಿಂದಿನ ಪೋಸ್ಟ್‌ನಲ್ಲಿ ಈಗಾಗಲೇ ಚರ್ಚಿಸಿದ್ದೇವೆ. ನೀವು ಅದನ್ನು ಪರಿಶೀಲಿಸಬಹುದು ಇಲ್ಲಿ.

ಉದಾಹರಣೆ

n = 5, r = 2, p = 6
4

ವಿವರಣೆ

nCr = 5C2 = 10
nCr% p = 10% 6 = 4
ಆದ್ದರಿಂದ, ದ್ವಿಪದ ಗುಣಾಂಕದ ಸೂತ್ರವನ್ನು ಬಳಸಿಕೊಂಡು ನಾವು 5 ಸಿ 2 ಅನ್ನು ಲೆಕ್ಕ ಹಾಕಿದ್ದೇವೆ. ನಂತರ ಮೌಲ್ಯದ ಮೇಲೆ ಮಾಡ್ಯುಲೋವನ್ನು ತೆಗೆದುಕೊಂಡರು.

NCr% p ಅನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಿ

ಅಪ್ರೋಚ್

ದ್ವಿಪದ ಗುಣಾಂಕದ ಲೆಕ್ಕಾಚಾರಕ್ಕೆ ಸಂಬಂಧಿಸಿದ ಹಿಂದಿನ ಪೋಸ್ಟ್‌ನಲ್ಲಿ. ನಾವು ಮಾಡಿದ್ದು ಮೊದಲು ಎನ್‌ಸಿಆರ್ ಅನ್ನು ಪರಿಹರಿಸಲು ಅಗತ್ಯವಿರುವ ಮೌಲ್ಯಗಳನ್ನು ಲೆಕ್ಕಹಾಕಲಾಗಿದೆ. ನಾವು ಬಳಸಿದ್ದೇವೆ ಡೈನಾಮಿಕ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಆದರೆ ನಾವು nCr ನ ಮೌಲ್ಯವನ್ನು ಮಾತ್ರ ಲೆಕ್ಕ ಹಾಕುತ್ತಿದ್ದೆವು. ದ್ವಿಪದ ಗುಣಾಂಕ ಮಾಡ್ಯುಲೋ ಅಲ್ಲ ಕೆಲವು ಸಂಖ್ಯೆ p. ನಿಷ್ಕಪಟ ವಿಧಾನವೆಂದರೆ ಮೊದಲು ದ್ವಿಪದ ಗುಣಾಂಕವನ್ನು ಲೆಕ್ಕಹಾಕುವುದು ಮತ್ತು ನಂತರ ಮಾಡ್ಯುಲೋ p ಅನ್ನು ತೆಗೆದುಕೊಳ್ಳುವುದು. ಆದರೆ ಈ ಲೆಕ್ಕಾಚಾರಕ್ಕೆ ಒಂದು ಮಿತಿ ಇದೆ. ದೊಡ್ಡ ಸಂಖ್ಯೆಯಲ್ಲಿ ನೀವು ದ್ವಿಪದ ಗುಣಾಂಕಗಳನ್ನು ಲೆಕ್ಕಹಾಕಲು ಸಾಧ್ಯವಿಲ್ಲ ಏಕೆಂದರೆ ಅದು ಉಕ್ಕಿ ಹರಿಯುತ್ತದೆ. ಆದ್ದರಿಂದ ಪೂರ್ಣಾಂಕದ ಉಕ್ಕಿ ಹರಿಯದೆ ಸರಿಯಾದ ಫಲಿತಾಂಶವನ್ನು ನೀಡುವ ಮಾರ್ಗವನ್ನು ನಾವು ಕಂಡುಹಿಡಿಯಬೇಕು.

ನಮ್ಮ ದ್ವಿಪದ ಗುಣಾಂಕದ ಲೆಕ್ಕಾಚಾರ ಮಾಡುವಾಗ ನಾವು ಮಾಡ್ಯುಲಸ್ ತೆಗೆದುಕೊಳ್ಳುವುದನ್ನು ಮುಂದುವರಿಸಬಹುದು. ಆದ್ದರಿಂದ ಹಿಂದಿನ ಪೋಸ್ಟ್‌ನ ಪರಿಹಾರದ ಏಕೈಕ ಬದಲಾವಣೆಯೆಂದರೆ, ನಾವು ಲೆಕ್ಕಾಚಾರದ ಸಮಯದಲ್ಲಿ ಮಾಡ್ಯುಲಸ್ ಅನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತೇವೆ. ಹೀಗೆ ನಮ್ಮ ಪುನರಾವರ್ತಿತ ಸೂತ್ರವು ಸ್ವಲ್ಪ ಬದಲಾಗುತ್ತದೆ, ಆದರೆ ಪರಿವರ್ತನೆಗಳು ಒಂದೇ ಆಗಿರುತ್ತವೆ. ಮತ್ತು ಪ್ರಸ್ತುತ ದ್ವಿಪದ ಗುಣಾಂಕವು ಮೊದಲಿನಂತೆಯೇ ಅದೇ ರಾಜ್ಯಗಳ ಮೇಲೆ ಅವಲಂಬಿತವಾಗಿರುತ್ತದೆ.

ಕೋಡ್

NCr% p ಅನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು C ++ ಕೋಡ್

#include<bits/stdc++.h>
using namespace std;
// this function just makes our pascal triangle
int computeBinomialCoefficientsModuloP(int n, int r, int p)
{
  int C[r+1];
    C[0] = 1;
    for (int i = 0; i <= n; i++)
    {
        // since the recursive formula is dependent on current and previous binomial coefficient on i
        // if we had run a forward loop our algorithm would have not given us a correct result
        for (int j = min(i, r); j >0 ; j--)
        {
            C[j] = (C[j - 1] + C[j])%p; // use recursive formula
        }
    }
    return C[r];
}

int main()
{
    int n,k,p;cin>>n>>k>>p;
    // here n & k do not satisfy the properties of binomial coefficient
    // then we will answer it as 0
    int val = computeBinomialCoefficientsModuloP(n, k, p);
    if(val != 0)
      cout<<val<<endl;
    else
      cout<<0<<endl;
}
5 2 4
2

NCr% p ಅನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಜಾವಾ ಕೋಡ್

import java.util.*;
class Main{
  // this function just makes our pascal triangle
  static int computeBinomialCoefficientsModuloP(int n, int r, int p) 
  {
  	int C[] = new int[r+1];
  	C[0] = 1;
    for (int i = 0; i <= n; i++) 
    { 
      // since the recursive formula is dependent on current and previous binomial coefficient on i
      // if we had run a forward loop our algorithm would have not given us a correct result 
      for (int j = Math.min(i, r); j >0 ; j--) 
      {
          C[j] = (C[j - 1] + C[j])%p; // use recursive formula
      }
    } 
    return C[r]; 
  }
  
  public static void main(String[] args)
  {
      Scanner sc = new Scanner(System.in);
      // 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();
      int p = sc.nextInt();
      int val = computeBinomialCoefficientsModuloP(n, k, p);
      if(val != 0)
        System.out.println(val);    
      else
        System.out.println(0);
   }
}
5 2 4
2

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್ * ಆರ್), ಇಲ್ಲಿ N ಮತ್ತು R ಅನ್ನು ನೀಡಿದ ಒಳಹರಿವು. ನಮ್ಮ ದ್ವಿಪದ ಗುಣಾಂಕವನ್ನು ನಾವು ಲೆಕ್ಕಾಚಾರ ಮಾಡುವಾಗ, ನಾವು ಹೊರಗಿನ ಲೂಪ್ ಮತ್ತು ಒಂದು ಆಂತರಿಕ ಲೂಪ್ ಅನ್ನು ಹೊಂದಿದ್ದೇವೆ ಎಂಬುದು ಇದಕ್ಕೆ ಕಾರಣ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಆರ್), ಮಧ್ಯಂತರ ಮೌಲ್ಯಗಳನ್ನು ಸಂಗ್ರಹಿಸಲು ನಾವು ಒಂದು ಶ್ರೇಣಿಯನ್ನು ಮಾಡಿದ್ದೇವೆ ಮತ್ತು ಆದ್ದರಿಂದ ಸ್ಥಳದ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿರುತ್ತದೆ.