Java में n के भाजकों को गिनें जिनमें n के साथ कम से कम एक अंक समान हो

दिया गया एक संख्या num, हमें उन भाजकों (divisors) की संख्या गिननी है जिनमें num के साथ कम से कम एक अंक (digit) समान हो।

समस्या विश्लेषण

उदाहरण 1: num = 24

• 24 के भाजक: 1, 2, 3, 4, 6, 8, 12, 24
• 24 के अंक: {2, 4}
• मिलान वाले भाजक: 2 (2 है), 4 (4 है), 12 (2 है), 24 (2, 4 हैं)
• आउटपुट: 4

उदाहरण 2: num = 10

• 10 के भाजक: 1, 2, 5, 10
• 10 के अंक: {1, 0}
• मिलान वाले भाजक: 1 (1 है), 10 (1, 0 हैं)
• आउटपुट: 2

कुशल एल्गोरिदम

1. संख्या के सभी अंकों को एक बूलियन ऐरे या Set में संग्रहीत करें।
2. 1 से √n तक पुनरावृति करके भाजक खोजें (O(√n) समय जटिलता)।
3. प्रत्येक भाजक जोड़ी (i, n/i) के लिए, जांचें कि क्या किसी में मूल संख्या का कोई अंक है।
4. मान्य भाजकों की गणना करें।

Java कार्यान्वयन

import java.util.HashSet;
import java.util.Set;

public class DivisorDigitMatch {
    
    public static int countDivisorsWithCommonDigit(int n) {
        // चरण 1: मूल संख्या के सभी अंकों को एक सेट में संग्रहीत करें
        Set digits = new HashSet<>();
        int temp = n;
        while (temp > 0) {
            digits.add(temp % 10);
            temp /= 10;
        }
        // एज केस: n = 0 (हालांकि भाजक समस्या के लिए आमतौर पर n > 0)
        if (n == 0) digits.add(0);
        
        int count = 0;
        
        // चरण 2: √n तक भाजक खोजें
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                // पहला भाजक: i
                if (hasCommonDigit(i, digits)) {
                    count++;
                }
                
                // दूसरा भाजक: n/i (यदि अलग है)
                int pairedDivisor = n / i;
                if (pairedDivisor != i && hasCommonDigit(pairedDivisor, digits)) {
                    count++;
                }
            }
        }
        return count;
    }
    
    // सहायक विधि: जांचें कि क्या संख्या में सेट से कोई अंक है
    private static boolean hasCommonDigit(int number, Set digitSet) {
        if (number == 0) return digitSet.contains(0);
        while (number > 0) {
            if (digitSet.contains(number % 10)) {
                return true;
            }
            number /= 10;
        }
        return false;
    }
    
    public static void main(String[] args) {
        // टेस्ट केस
        System.out.println("n=24: " + countDivisorsWithCommonDigit(24)); // 4
        System.out.println("n=10: " + countDivisorsWithCommonDigit(10)); // 2
        System.out.println("n=15: " + countDivisorsWithCommonDigit(15)); // 3 (1, 3, 5, 15 -> 1,3,5,15 सभी में 1 या 5 है)
        System.out.println("n=7: " + countDivisorsWithCommonDigit(7));   // 1 (1, 7 -> केवल 7)
        System.out.println("n=100: " + countDivisorsWithCommonDigit(100)); // 5 (1,2,4,5,10,20,25,50,100 -> 1,10,20,50,100)
    }
}

समय और स्थान जटिलता

• समय जटिलता: O(√n * d) जहां d भाजक में अंकों की संख्या है (अधिकतम log₁₀n)। प्रभावी रूप से बड़ी संख्याओं के लिए O(√n log n)।
• स्थान जटिलता: अंक सेट के लिए O(1) (अधिकतम 10 अंक) + कॉल स्टैक के लिए O(1)।

मूल कोड में बग फिक्स

दिए गए मूल कोड में एक बग था: यह ans प्रिंट करता था जो घोषित नहीं था (सही चर count है)। साथ ही, 10 के लिए उदाहरण व्याख्या में गलती से "24 के भाजक" लिखा था। उपरोक्त सही कार्यान्वयन इन मुद्दों को ठीक करता है।