Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Divisibility by 3 Check

EASYProblemSolveExternal Links

Description

Given a number represented as a string, determine whether it is divisible by 3.

The number can be extremely large — so large that it cannot be stored in standard integer data types like int or long long in languages such as C++ and Java. You must handle numbers of arbitrary length.

Return "Yes" if the number is divisible by 3, otherwise return "No".

Examples

Example 1

Input: n = "769452"

Output: Yes

Explanation: 769452 ÷ 3 = 256484, which is an exact division with no remainder. Equivalently, the sum of its digits is 7 + 6 + 9 + 4 + 5 + 2 = 33, and 33 is divisible by 3.

Example 2

Input: n = "123456758933312"

Output: No

Explanation: The sum of its digits is 1 + 2 + 3 + 4 + 5 + 6 + 7 + 5 + 8 + 9 + 3 + 3 + 3 + 1 + 2 = 62. Since 62 is not divisible by 3 (62 = 3 × 20 + 2, remainder 2), the number is not divisible by 3.

Example 3

Input: n = "3635883959606670431112222"

Output: Yes

Explanation: This number is extremely large and cannot fit in a standard 64-bit integer. The sum of its digits is 3 + 6 + 3 + 5 + 8 + 8 + 3 + 9 + 5 + 9 + 6 + 0 + 6 + 6 + 7 + 0 + 4 + 3 + 1 + 1 + 1 + 2 + 2 + 2 + 2 = 102. Since 102 ÷ 3 = 34 exactly, the number is divisible by 3.

Constraints

  • 1 ≤ |n| ≤ 10^5 (length of the number string)
  • n consists of digits '0' to '9' only
  • n does not contain leading zeros (except for the number "0" itself)

Editorial

Brute Force

Intuition

The most direct way to check divisibility is to compute the number modulo 3. Since the number can be very large (potentially hundreds of thousands of digits), we cannot simply convert the entire string to an integer in languages like C++ or Java — it would overflow. Instead, we process the string digit by digit, maintaining a running remainder.

The key mathematical insight is that we can build up the number's remainder incrementally. If we have processed the first k digits and the accumulated remainder is r, then processing the next digit d gives us a new remainder of (r × 10 + d) % 3. This works because:

  • The first k digits represent some number N where N % 3 = r
  • Appending digit d means the full number so far is N × 10 + d
  • So the new remainder is (N × 10 + d) % 3 = (r × 10 + d) % 3

Think of it like reading the number left to right, one digit at a time, and always keeping track of "what would the remainder be if we divided everything we've read so far by 3?" At the end, if the remainder is 0, the full number is divisible by 3.

Step-by-Step Explanation

Let's trace through with n = "769452" (Example 1):

Step 1: Initialize remainder = 0.

Step 2: Process digit '7': remainder = (0 × 10 + 7) % 3 = 7 % 3 = 1.

Step 3: Process digit '6': remainder = (1 × 10 + 6) % 3 = 16 % 3 = 1.

Step 4: Process digit '9': remainder = (1 × 10 + 9) % 3 = 19 % 3 = 1.

Step 5: Process digit '4': remainder = (1 × 10 + 4) % 3 = 14 % 3 = 2.

Step 6: Process digit '5': remainder = (2 × 10 + 5) % 3 = 25 % 3 = 1.

Step 7: Process digit '2': remainder = (1 × 10 + 2) % 3 = 12 % 3 = 0.

Result: remainder = 0 → The number IS divisible by 3. Return "Yes".

Running Modulo — Processing Digits Left to Right — Watch how we maintain a running remainder as we process each digit of '769452'. At each step we compute (remainder × 10 + digit) % 3.

Algorithm

  1. Initialize remainder = 0
  2. For each character ch in the string from left to right:
    a. Convert ch to its numeric digit value d
    b. Update remainder = (remainder × 10 + d) % 3
  3. If remainder == 0, return "Yes" (divisible by 3)
  4. Otherwise, return "No"

Code

#include <string>
using namespace std;

class Solution {
public:
    bool isDivisibleBy3(string s) {
        int remainder = 0;
        for (int i = 0; i < s.length(); i++) {
            remainder = (remainder * 10 + (s[i] - '0')) % 3;
        }
        return remainder == 0;
    }
};
class Solution:
    def isDivisibleBy3(self, s: str) -> bool:
        remainder = 0
        for ch in s:
            remainder = (remainder * 10 + int(ch)) % 3
        return remainder == 0
class Solution {
    public boolean isDivisibleBy3(String s) {
        int remainder = 0;
        for (int i = 0; i < s.length(); i++) {
            remainder = (remainder * 10 + (s.charAt(i) - '0')) % 3;
        }
        return remainder == 0;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through every digit of the string exactly once. At each step, we perform a constant-time multiplication, addition, and modulo operation. So the total time is proportional to the number of digits n.

Space Complexity: O(1)

We only use a single integer variable remainder regardless of the input size. No additional data structures are needed.

While this approach is already linear in time, it performs a multiplication (remainder × 10) and a modulo operation at every step. A deeper mathematical observation can simplify the per-step computation — removing the multiplication entirely.

Why This Approach Is Not Efficient

Although the running modulo approach is already O(n) time and O(1) space, it performs more arithmetic than strictly necessary at each step:

  1. Unnecessary multiplication: At each step, we compute remainder × 10 + digit, which simulates how positional notation works. But for divisibility by 3 specifically, we don't need to track the full positional remainder.

  2. Missing a mathematical shortcut: There is a beautiful mathematical property unique to divisibility by 3: because 10 ≡ 1 (mod 3), every power of 10 also gives remainder 1 when divided by 3. This means:

    • A number like 769452 = 7×10⁵ + 6×10⁴ + 9×10³ + 4×10² + 5×10¹ + 2×10⁰
    • Modulo 3: ≡ 7×1 + 6×1 + 9×1 + 4×1 + 5×1 + 2×1 = 7 + 6 + 9 + 4 + 5 + 2

    So the remainder of the number divided by 3 is exactly the same as the remainder of the sum of its digits divided by 3!

This means we can replace the multiplication-based running remainder with a simple digit sum. Each step reduces from a multiply-add-modulo to just a single addition. The code becomes shorter, the logic becomes cleaner, and the mathematical insight makes the solution more elegant and memorable.

Optimal Approach - Digit Sum Divisibility Rule

Intuition

There is a well-known divisibility rule: a number is divisible by 3 if and only if the sum of its digits is divisible by 3.

Why does this work? It comes from the fact that 10 leaves a remainder of 1 when divided by 3 (since 10 = 3 × 3 + 1). This means:

  • 10¹ ≡ 1 (mod 3)
  • 10² = 100 ≡ 1 (mod 3)
  • 10³ = 1000 ≡ 1 (mod 3)
  • In general, 10ⁿ ≡ 1 (mod 3) for any n ≥ 0

So when we write a number in decimal notation, each digit's contribution to the remainder modulo 3 is simply the digit itself — because its positional multiplier 10ⁿ ≡ 1. The total remainder equals the sum of all the digits modulo 3.

For example, 1332 = 1×1000 + 3×100 + 3×10 + 2×1. Modulo 3, this becomes 1×1 + 3×1 + 3×1 + 2×1 = 1 + 3 + 3 + 2 = 9. Since 9 % 3 = 0, the number 1332 is divisible by 3.

This approach is beautifully simple: just add up all the digits and check if their sum is divisible by 3. No multiplication, no running remainder — just pure addition.

Step-by-Step Explanation

Let's trace through with n = "769452" (Example 1):

Step 1: Initialize digitSum = 0.

Step 2: Add digit '7': digitSum = 0 + 7 = 7.

Step 3: Add digit '6': digitSum = 7 + 6 = 13.

Step 4: Add digit '9': digitSum = 13 + 9 = 22.

Step 5: Add digit '4': digitSum = 22 + 4 = 26.

Step 6: Add digit '5': digitSum = 26 + 5 = 31.

Step 7: Add digit '2': digitSum = 31 + 2 = 33.

Step 8: Check divisibility: 33 % 3 = 0 → Return "Yes".

The sum 33 is divisible by 3, confirming that 769452 is divisible by 3.

Now let's verify with n = "123456758933312" (Example 2):

Digit sum = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 5 + 8 + 9 + 3 + 3 + 3 + 1 + 2 = 62.
62 % 3 = 2 (since 62 = 3 × 20 + 2) → Not divisible. Return "No".

Digit Sum — Accumulate and Check — Watch how we simply add up all digits of '769452' and check if the total is divisible by 3. No multiplication needed — just pure addition powered by the elegant property 10ⁿ ≡ 1 (mod 3).

Algorithm

  1. Initialize digitSum = 0
  2. For each character ch in the string:
    a. Convert ch to its numeric digit value d
    b. Add d to digitSum
  3. If digitSum % 3 == 0, return "Yes" (divisible by 3)
  4. Otherwise, return "No"

Code

#include <string>
using namespace std;

class Solution {
public:
    bool isDivisibleBy3(string s) {
        int digitSum = 0;
        for (int i = 0; i < s.length(); i++) {
            digitSum += (s[i] - '0');
        }
        return digitSum % 3 == 0;
    }
};
class Solution:
    def isDivisibleBy3(self, s: str) -> bool:
        digit_sum = sum(int(ch) for ch in s)
        return digit_sum % 3 == 0
class Solution {
    public boolean isDivisibleBy3(String s) {
        int digitSum = 0;
        for (int i = 0; i < s.length(); i++) {
            digitSum += (s.charAt(i) - '0');
        }
        return digitSum % 3 == 0;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through each digit of the string exactly once, performing a single addition per digit. The final modulo check is O(1). Total time is O(n) where n is the number of digits.

Space Complexity: O(1)

We use a single integer variable digitSum regardless of the input size. No additional data structures are needed.

Why this is optimal: We must read every digit at least once — any single digit could change the divisibility result — so O(n) is a lower bound on time. This solution achieves that lower bound with the minimal possible work per digit (one addition), and uses only O(1) extra space. The mathematical insight that 10ⁿ ≡ 1 (mod 3) transforms what could have been a complex modular arithmetic problem into the simplest possible summation check.