పెయింటింగ్ కంచె అల్గోరిథం


కఠినత స్థాయి హార్డ్
తరచుగా అడుగుతుంది కోడ్‌నేషన్ <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> గూగుల్ Intuit జెపి మోర్గాన్ మోర్గాన్ స్టాన్లీ
అర్రే డైనమిక్ ప్రోగ్రామింగ్ లీట్‌కోడ్

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

“పెయింటింగ్ కంచె అల్గోరిథం” మీకు కొన్ని పోస్టులు (కొన్ని చెక్క ముక్కలు లేదా కొన్ని ఇతర ముక్కలు) మరియు కొన్ని రంగులను కలిగి ఉన్న కంచెని ఇస్తుందని పేర్కొంది. కంచెను చిత్రించడానికి అనేక మార్గాలను కనుగొనండి, అంటే కేవలం 2 ప్రక్కనే ఉన్న కంచెలు ఒకే రంగులో ఉంటాయి. ఈ సంఖ్య పెద్దదిగా ఉన్నందున, మాడ్యులో 1000000007 సమాధానం ఇవ్వండి.

ఉదాహరణ

పెయింటింగ్ కంచె అల్గోరిథం

Number of posts/wooden sticks = 2
Number of colors = 2
4

వివరణ
మీరు రెండు పోస్ట్‌లను వేర్వేరు రంగులతో 2 విధాలుగా చిత్రించవచ్చు. మరియు పోస్టులను ఒకే రంగుతో చిత్రించడానికి మీకు 2 మార్గాలు ఉన్నాయి. కాబట్టి మొత్తం మీకు 4 మార్గాలు ఉన్నాయి.

పెయింటింగ్ కంచె అల్గోరిథం కోసం విధానం

అమాయక విధానంతో ప్రారంభిద్దాం. మనకు n పోస్ట్లు మరియు k రంగులు ఉన్నాయని ఇవ్వబడింది. ఒకే రంగుతో గరిష్టంగా 2 ప్రక్కనే ఉన్న పోస్టులు మాత్రమే ఉన్న పోస్టులకు రంగులు వేసే మార్గాల సంఖ్యను ఇప్పుడు మనం కనుగొనాలి. మనం ఉంటే ఒక అమాయక విధానం కావచ్చు అన్ని సన్నివేశాలను ఉత్పత్తి చేస్తుంది ప్రతి పోస్ట్ ద్వారా పొందిన రంగును సూచిస్తుంది. కానీ ఈ విధానం చాలా అసమర్థమైనది మరియు తప్పనిసరిగా సమయ పరిమితిని మించిపోతుంది.

కాబట్టి, మంచి విధానం ఏమిటి? ఒకటి విధానం మేము సమస్యను చిన్న సమస్యలుగా విభజిస్తే కావచ్చు. పోస్టుల సంఖ్య = n-2 మరియు n-1 లకు సమాధానం మనకు తెలుసు. ఈ విలువలను వరుసగా F (n-2) మరియు F (n-1) ఉపయోగించి సూచిద్దాం. కాబట్టి F (n-1) గరిష్టంగా 2 ప్రక్కనే ఉన్న పోస్టులు ఒకే రంగును కలిగి ఉన్న మార్గాల సంఖ్యను సూచిస్తుందని మనకు తెలుసు మరియు F (n-2) కు ఇది వర్తిస్తుంది. ఇప్పుడు మేము (n-1) వ మరియు n వ స్థానంలో ఒకే రంగుతో పోస్టులను కలర్ చేస్తే, (n-1) వ పోస్ట్ (n-2) nd పోస్ట్ యొక్క రంగును కలిగి ఉండకూడదు. ఈ విలువ F (n-2) ఉపయోగించి సూచించబడుతుంది. కాబట్టి మా n వ పోస్ట్ చివరి పోస్ట్ మాదిరిగానే ఉంటుంది. ప్రస్తుత పోస్ట్ మరియు చివరి పోస్ట్ ఒకే రంగును కలిగి ఉండకూడని మార్గాలను కూడా మనం పరిగణించాలి. ఈ విలువ F (n-1) ఉపయోగించి సూచించబడుతుంది. ఇప్పుడు మనకు (k-1) n వ పోస్ట్ రంగు వేయడానికి మార్గాలు ఉన్నాయి. ఈ విధంగా మొత్తం మార్గాల సంఖ్య (F (n-1) + F (n-2)) * (k-1) కు సమానం.

కోడ్

పెయింటింగ్ కంచె అల్గోరిథం కోసం సి ++ కోడ్

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

int main(){
  // number of posts
  int n;cin>>n;
  // number of available colors
  int k;cin>>k;
  int mod = 1000000007;
  int ways = 0;
  if(n == 1)cout<<k;
  else if(n == 2)cout<<k*k;
  else {
    int last = k*k; int lastTolast = k;
    for(int i=3;i<=n;i++){
      ways = ((last + lastTolast)*(k-1))%mod;
      lastTolast = last;
      last = ways;
    }
    cout<<ways;
  }
}
4 2
10

పెయింటింగ్ కంచె అల్గోరిథం కోసం జావా కోడ్

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    	// number of posts
    int n = sc.nextInt();
    // number of available colors
    int k = sc.nextInt();
    int mod = 1000000007;
    int ways = 0;
    if(n == 1)System.out.print(k);
    else if(n == 2)System.out.print(k*k);
    else {
      int last = k*k; int lastTolast = k;
      for(int i=3;i<=n;i++){
        ways = ((last + lastTolast)*(k-1))%mod;
        lastTolast = last;
        last = ways;
      }
      System.out.print(ways);
    }
    }
}
4 2
10

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

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

పై), మేము అల్గోరిథం నుండి చూడవచ్చు. నేను n కి సమానమయ్యే వరకు నడిచే ఒకే లూప్‌ను ఉపయోగించాము. ఈ విధంగా n పునరావృత్తులు చేయడం, అంటే మనకు సరళ సమయ సంక్లిష్టత ఉంది.

స్థల సంక్లిష్టత

ఓ (1),  మేము DP శ్రేణిని చేయడానికి బదులుగా స్థిరమైన వేరియబుల్స్ సంఖ్యను ఉపయోగించాము. ఈ విధానం మరింత ఆచరణీయమైనది ఎందుకంటే సమస్యకు పరిష్కారం చివరి రెండు చిన్న సమస్యలపై మాత్రమే ఆధారపడి ఉంటుంది.