एन समाधान द्वारा विभाजित गैर-संगत तत्व

Question

एन द्वारा विभाजित पूर्णांक के दिए गए सरणी के गैर संगत उप-अनुक्रमों की संख्या को गिनने का एक प्रभावी तरीका क्या है? एक = {1,2,3,2} n = 6 आउटपुट क्योंकि 12, 12, 132 6

मेरे समाधान जो गतिशील प्रोग्रामिंग मुझे गलत परिणाम दे रहा है का उपयोग करता है से विभाज्य है। यह हमेशा मुझे वास्तविक परिणाम से एक और दे रहा है।

#include <stdio.h> 

#define MAXLEN 100 
#define MAXN 100 
int len = 1,ar[] = {1, 6, 2},dp[MAXLEN][MAXN],n=6; 

int fun(int idx,int m) 
{ 
    if (idx >= (sizeof(ar)/sizeof(ar[0]))) 
     return m == 0; 
    if(dp[idx][m]!=-1) 
     return dp[idx][m]; 
    int ans=fun(idx+1,m);    // skip this element in current sub-sequence 
    ans+=fun(idx+1,(m*10+ar[idx])%n); // Include this element. Find the new modulo by 'n' and pass it recursively 
    return dp[idx][m]=ans; 
} 
int main() 
{ 
    memset(dp, -1, sizeof(dp)); 
    printf("%d\n",fun(0, 0));   // initially we begin by considering array of length 1 i.e. upto index 0 
    return 0; 
} 

कोई भी गलती को इंगित कर सकता है?

Answer 1

समस्या यह है कि "रिक्त" अनुक्रम को समाधान माना जाता है (m == 0 जब आप कॉल शुरू करते हैं और कोई भी अंक नहीं जोड़ते हैं तो आपको अंत में m == 0 के साथ छोड़ दिया जाएगा)।

या तो यह सही है लेकिन फिर {1, 2, 3, 2} के लिए समाधान 4 है, या आपको fun(0, 0)-1 उत्तर देने के द्वारा इसे घटाना होगा।