โปรแกรม Java หาเลข K หลักที่เล็กที่สุดที่หาร X ลงตัว

โจทย์: Smallest K-digit Number Divisible by X

หาเลขที่มี K digits อย่างน้อย (คือ ≥ 10^(K-1)) ที่หาร X ลงตัว

สูตร

Min K-digit = 10^(K-1)
ถ้า 10^(K-1) % X == 0 → คำตอบ = 10^(K-1)
มิฉะนั้น → คำตอบ = 10^(K-1) + (X - 10^(K-1) % X)

ตัวอย่างโค้ด

public class Demo {
    public static long smallestKDigitDivisibleByX(long x, int k) {
        if (k <= 0) throw new IllegalArgumentException("k must be positive");
        if (x <= 0) throw new IllegalArgumentException("x must be positive");
        
        // 10^(k-1) - careful with overflow for large k
        long minKDigit = 1;
        for (int i = 1; i < k; i++) {
            minKDigit *= 10;
            // Check overflow
            if (minKDigit < 0) throw new ArithmeticException("k too large for long");
        }
        
        long remainder = minKDigit % x;
        if (remainder == 0) {
            return minKDigit;
        } else {
            return minKDigit + (x - remainder);
        }
    }
    
    // BigInteger version for arbitrary large k
    public static java.math.BigInteger smallestKDigitDivisibleByXBig(java.math.BigInteger x, int k) {
        java.math.BigInteger minKDigit = java.math.BigInteger.TEN.pow(k - 1);
        java.math.BigInteger rem = minKDigit.mod(x);
        if (rem.equals(java.math.BigInteger.ZERO)) {
            return minKDigit;
        } else {
            return minKDigit.add(x.subtract(rem));
        }
    }
    
    public static void main(String[] args) {
        long x = 76;
        int k = 3;
        
        System.out.println("X = " + x + ", K = " + k);
        System.out.println("Smallest " + k + "-digit divisible by " + x + ": " + 
                          smallestKDigitDivisibleByX(x, k));
        
        // Verify
        long result = smallestKDigitDivisibleByX(x, k);
        System.out.println("Check: " + result + " % " + x + " = " + (result % x));
        System.out.println("Digits: " + String.valueOf(result).length());
    }
}

ผลลัพธ์

X = 76, K = 3
Smallest 3-digit divisible by 76: 152
Check: 152 % 76 = 0
Digits: 3

Complexity

• Time: O(k) สำหรับคำนวณ 10^(k-1) (หรือ O(log k) ด้วย exponentiation by squaring)
• Space: O(1)

Edge Cases

• X = 1 → คำตอบ = 10^(K-1)
• K = 1 → คำตอบ = X (ถ้า X < 10) หรือไม่มีคำตอบ (ถ้า X ≥ 10)
• X มีหลักมากกว่า K → ไม่มีคำตอบ