Check if a Large Number is Divisible by 9

31
0

Given a string s representing a non-negative integer in decimal form, process its digits directly from the string. Return true if the represented integer is divisible by 9 and false otherwise.

Example 1

Input: s = "58307142968531476290"

Output: true

Explanation: The digits add up to 90. Since 90 is a multiple of 9, the number represented by s is divisible by 9.

Example 2

Input: s = "1"

Output: false

Explanation: The digit sum is 1, which leaves a remainder of 1 when divided by 9.

Approach

The number may be too large to fit in a standard numeric type, so the check needs to work directly with its digits. The divisibility rule for 9 gives a useful shortcut. A number is divisible by 9 exactly when the sum of its digits is divisible by 9. This works because every decimal place value leaves a remainder of 1 when divided by 9, giving the whole number and its digit sum the same remainder.

Only the remainder of that sum is needed to decide the answer. Removing a complete multiple of 9 from a partial sum has no effect on the final remainder. Keeping the remainder as digits are added is therefore enough, and its value stays between 0 and 8.

A final remainder of 0 means both the digit sum and the original number are divisible by 9.

Algorithm

  • Start with a remainder of 0 for the digits processed so far.

  • Read the characters of s from left to right, converting each character to its numeric digit value.

  • Add the digit to the current remainder.

  • Keep only the remainder after dividing the updated value by 9.

  • Continue until every digit has been processed, including for a one-character input. Return true if the final remainder is 0 and false otherwise.

Dry Run

Check if a Large Number is Divisible by 9

Check if a Large Number is Divisible by 9

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns whether the decimal string represents a multiple of 9.
bool isDivisibleBy9(const string& s) {
int remainder = 0;
// Read each digit and keep the digit sum modulo 9.
for (char ch : s) {
int digit = ch - '0';
remainder = (remainder + digit) % 9;
}
return remainder == 0;
}
};
// Driver code
int main() {
const string s = "58307142968531476290";
// instance for class Solution
Solution sol;
cout << boolalpha << sol.isDivisibleBy9(s) << '\n';
return 0;
}

Complexity Analysis

Time Complexity: O(N) because each digit is processed once.

Space Complexity: O(1) auxiliary space because the scan stores only a fixed number of scalar values.

Interview follow-up Questions

Yes. 0 = 9 × 0, so "0" returns true. In variants that allow leading zeros, those zeros add nothing to the digit sum and have no effect on the result.

MathsTCS NQT

Read Similar Blogs

Comments0