इष्टतम एल्गोरिदम को किसी दिए गए पूर्णांक के द्वारा विभाजित जोड़े खोजने के लिए आवश्यक

Question

दिए गए एन पूर्णांक और एक पूर्णांक के, यह बताएं कि दिए गए एन पूर्णांक के कितने जोड़े मौजूद हैं कि जोड़ी में दो तत्वों का योग के द्वारा विभाजित किया जा सकता है?

मुझे एन और के पर सीमाएं नहीं पता हैं। तो, सादगी के लिए, मान लें कि एन और के बहुत बड़े नहीं हैं।

यह कहने के बिना चला जाता है, यथासंभव इष्टतम समाधान के रूप में दें। (मुझे मूर्ख विधि पता है :-)!)

Answer 1

चाहे k द्वारा दो संख्याओं का योग विभाजित हो, केवल उनके रहने वाले मॉड्यूल k पर निर्भर करता है।

तो k उचित रूप से छोटा है, तो आप केवल यह अनुमान लगा सकते हैं कि प्रत्येक संभव शेष कितनी संख्या है और उससे जोड़े की संख्या की गणना करें। k > 0 मान लिया जाये और सभी पूर्णांकों गैर नकारात्मक

unsigned long long combinations(unsigned k, unsigned long long *arr, unsigned n) { 
    unsigned long long counts[k] = {0}; 
    unsigned i; 
    for(i = 0; i < n; ++i) { 
     ++counts[arr[i]%k]; 
    } 
    // number of pairs where both are divisible by k 
    unsigned long long combs = counts[0]*(counts[0]-1)/2; 
    for(i = 1; i < (k+1)/2; ++i) { 
     combs += counts[i]*counts[k-i]; 
    } 
    if (k == 2*i) { 
     combs += counts[i]*(counts[i] - 1)/2; 
    } 
    return combs; 
} 

O(n+k) चरणों में काम करता है। यदि n छोटा है और k बहुत बड़ा है, तो बेवकूफ एल्गोरिदम बेहतर है।

Answer 2

डैनियल फिशर के अलावा, यदि के बहुत बड़ा है, तो आप संख्याओं को छोटा कर सकते हैं, और फिर दोनों सिरों से क्रमबद्ध सूची (0 मोड के मानों से निपटने के बाद) मध्य (के/2 मॉड के)। वह ओ (एन लॉग एन) है, जो ओ (एन^2) बेहतर है, यह मानते हुए कि आपका बेवकूफ एल्गोरिदम वास्तव में बेवकूफ है।