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
0for the digits processed so far.Read the characters of
sfrom 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
trueif the final remainder is0andfalseotherwise.
Dry Run
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 codeint 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.
Be the first to add a comment.