Divisible by 13

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Check if large number (given as string) is divisible by 13. Iterative modulo on digits.

Algorithm

1Process digit by digit: remainder = (remainder * 10 + digit) % 13.

Common Pitfalls

•Standard modular arithmetic for large numbers. O(n) where n = number of digits.

Divisible by 13.java

Java

// Approach: Weighted digit sum modulo. Each digit position has a weight in {1,3,4,12,9,10} (mod 13 powers of 10).
// Time: O(n) Space: O(1)
class Solution {
    public boolean divby13(String s) {
        // Stores running remainder
        int rem = 0;

        // Process each digit and compute
        // remainder modulo 13
        for (int i = 0; i < s.length(); i++) {
            rem = (rem * 10 + (s.charAt(i) - '0')) % 13;
        }

        // Final check: if remainder is 0, number
        // is divisible by 13
        return rem == 0;
    }
}

Was this solution helpful?