You are given an n-digit large number, you have to check whether it is divisible by 999 without dividing or finding modulo of number by 999.
Examples:
Input : 235764 Output : Yes Input : 23576 Output : No
Since input number may be very large, we cannot use n % 999 to check if a number is divisible by 999 or not, especially in languages like C/C++. The idea is based on following fact.
The solutions is based on below fact.
A number is divisible by 999 if sum of its 3-digit-groups (if required groups are formed by appending a 0s at the beginning) is divisible by 999.
Illustration:
Input : 235764
Output : Yes
Explanation : Step I - read input : 235, 764
Step II - 235 + 764 = 999
As result is 999 then we can
conclude that it is divisible by 999.
Input : 1244633121
Output : Yes
Explanation : Step I - read input : 1, 244, 633, 121
Step II - 001 + 244 + 633 + 121 = 999
As result is 999 then we can conclude
that it is divisible by 999.
Input : 999999999
Output : Yes
Explanation : Step I - read input : 999, 999, 999
Step II - 999 + 999 + 999 = 2997
Step III - 997 + 002 = 999
As result is 999 then we can conclude
that it is divisible by 999.
How does this work?
Let us consider 235764, we can write it as
235764 = 2*105 + 3*104 + 5*103 +
7*102 + 6*10 + 4
The idea is based on below observation:
Remainder of 103 divided by 999 is 1
For i > 3, 10i % 999 = 10i-3 % 999
Let us see how we use above fact.
Remainder of 2*105 + 3*104 + 5*103 +
7*102 + 6*10 + 4
Remainder with 999 can be written as :
2*100 + 3*10 + 5*1 + 7*100 + 6*10 + 4
The above expression is basically sum of
groups of size 3.
Since the sum is divisible by 999, answer is yes.
A simple and efficient method is to take input in form of string (make its length in form of 3*m by adding 0 to left of number if required) and then you have to add the digits in blocks of three from right to left until it become a 3 digit number and if that result is 999 we can say that number is divisible by 999.
As in the case of “divisibility by 9” we check that sum of all digit is divisible by 9 or not, the same thing follows within the case of divisibility by 999. We sum up all 3-digits group from right to left and check whether the final result is 999 or not.
Implementation:
C++
// CPP for divisibility of number by 999 #include<bits/stdc++.h> using namespace std; // function to check divisibility bool isDivisible999(string num) { int n = num.length(); if (n == 0 && num[0] == '0') return true; // Append required 0s at the beginning. if (n % 3 == 1) num = "00" + num; if (n % 3 == 2) num = "0" + num; // add digits in group of three in gSum int gSum = 0; for (int i = 0; i<n; i++) { // group saves 3-digit group int group = 0; group += (num[i++] - '0') * 100; group += (num[i++] - '0') * 10; group += num[i] - '0'; gSum += group; } // calculate result till 3 digit sum if (gSum > 1000) { num = to_string(gSum); n = num.length(); gSum = isDivisible999(num); } return (gSum == 999); } // driver program int main() { string num = "1998"; int n = num.length(); if (isDivisible999(num)) cout << "Divisible"; else cout << "Not divisible"; return 0; } |
Java
//Java for divisibility of number by 999 class Test { // Method to check divisibility static boolean isDivisible999(String num) { int n = num.length(); if (n == 0 && num.charAt(0) == '0') return true; // Append required 0s at the beginning. if (n % 3 == 1) num = "00" + num; if (n % 3 == 2) num = "0" + num; // add digits in group of three in gSum int gSum = 0; for (int i = 0; i<n; i++) { // group saves 3-digit group int group = 0; group += (num.charAt(i++) - '0') * 100; group += (num.charAt(i++) - '0') * 10; group += num.charAt(i) - '0'; gSum += group; } // calculate result till 3 digit sum if (gSum > 1000) { num = Integer.toString(gSum); n = num.length(); gSum = isDivisible999(num) ? 1 : 0; } return (gSum == 999); } // Driver method public static void main(String args[]) { String num = "1998"; System.out.println(isDivisible999(num) ? "Divisible" : "Not divisible"); } } |
Python 3
# Python3 program for divisibility # of number by 999 # function to check divisibility def isDivisible999(num): n = len(num); if(n == 0 or num[0] == '0'): return true # Append required 0s at the beginning. if((n % 3) == 1): num = "00" + num if((n % 3) == 2): num = "0" + num # add digits in group of three in gSum gSum = 0 for i in range(0, n, 3): # group saves 3-digit group group = 0 group += (ord(num[i]) - 48) * 100 group += (ord(num[i + 1]) - 48) * 10 group += (ord(num[i + 2]) - 48) gSum += group # calculate result till 3 digit sum if(gSum > 1000): num = str(gSum) n = len(num) gSum = isDivisible999(num) return (gSum == 999) # Driver code if __name__=="__main__": num = "1998" n = len(num) if(isDivisible999(num)): print("Divisible") else: print("Not divisible") # This code is contributed # by Sairahul Jella |
C#
// C# code for divisibility of number by 999 using System; class Test { // Method to check divisibility static bool isDivisible999(String num) { int n = num.Length; if (n == 0 && num[0] == '0') return true; // Append required 0s at the beginning. if (n % 3 == 1) num = "00" + num; if (n % 3 == 2) num = "0" + num; // add digits in group of three in gSum int gSum = 0; for (int i = 0; i<n; i++) { // group saves 3-digit group int group = 0; group += (num[i++] - '0') * 100; group += (num[i++] - '0') * 10; group += num[i] - '0'; gSum += group; } // calculate result till 3 digit sum if (gSum > 1000) { num = Convert.ToString(gSum); n = num.Length ; gSum = isDivisible999(num) ? 1 : 0; } return (gSum == 999); } // Driver method public static void Main() { String num = "1998"; Console.WriteLine(isDivisible999(num) ? "Divisible" : "Not divisible"); } // This code is contributed by Ryuga } |
PHP
<?php // PHP for divisibility of number by 999 // function to check divisibility function isDivisible999($num) { $n = strlen($num); if ($n == 0 && $num[0] == '0') return true; // Append required 0s at the beginning. if ($n % 3 == 1) $num = "00" . $num; if ($n % 3 == 2) $num = "0" . $num; // add digits in group of three in gSum $gSum = 0; for ($i = 0; $i < $n; $i += 3) { // group saves 3-digit group $group = 0; $group += (ord($num[$i]) - 48) * 100; $group += (ord($num[$i + 1]) - 48) * 10; $group += (ord($num[$i + 2]) - 48); $gSum += $group; } // calculate result till 3 digit sum if ($gSum > 1000) { $num = strval($gSum); $n = strlen($num); $gSum = isDivisible999($num); } return ($gSum == 999); } // Driver Code $num = "1998"; if (isDivisible999($num)) echo "Divisible"; else echo "Not divisible"; // This code is contributed by mits ?> |
Javascript
<script> // Javascript for divisibility of number by 999 // function to check divisibility function isDivisible999(num) { let n = num.length; if (n == 0 && num[0] == '0') return true; // Append required 0s at the beginning. if (n % 3 == 1) num = "00" + num; if (n % 3 == 2) num = "0" + num; // add digits in group of three in gSum let gSum = 0; for (let i = 0; i < n; i += 3) { // group saves 3-digit group group = 0; group += (num.charCodeAt(i) - 48) * 100; group += (num.charCodeAt(i + 1) - 48) * 10; group += (num.charCodeAt(i + 2) - 48); gSum += group; } // calculate result till 3 digit sum if (gSum > 1000) { num = String(gSum); n = strlen(num); gSum = isDivisible999(num); } return (gSum == 999); } // Driver Code let num = "1998"; if (isDivisible999(num)) document.write("Divisible"); else document.write("Not divisible"); // This code is contributed by _saurabh_jaiswal. </script> |
Output
Divisible
Time complexity : O(n)
Auxiliary Space : O(1)
Method 2: Checking given any number is divisible by 999 or not by using modulo division operator “%”.
Implementation:
C++
#include <iostream> using namespace std; int main() { //input long long int n=235764; // finding given number is divisible by 999 or not if (n%999==0) { cout << "Yes"; } else { cout << "No"; } return 0; } // This code is contributed by satwik4409. |
Java
/*package whatever //do not write package name here */import java.io.*; class GFG { public static void main (String[] args) { // input long n = 235764; // finding given number is divisible by 999 or not if (n % 999 == 0) System.out.println("Yes"); else System.out.println("No"); } } // This code is contributed by ksrikanth0498. |
Python3
# Python code # To check whether the given number is divisible by 999 or not #input n=235764# the above input can also be given as n=input() -> taking input from user # finding given number is divisible by 999 or not if int(n)%999==0: print("Yes") else: print("No") # this code is contributed by gangarajula laxmi |
C#
// C# code // To check whether the given number is divisible by 999 or not using System; public class GFG{ static public void Main () { // input long n = 235764; // finding given number is divisible by 999 or not if (n % 999 == 0) Console.Write("Yes"); else Console.Write("No"); } } // This code is contributed by ksrikanth0498 |
PHP
<?php $num =235764; // checking if the given number is divisible by 999 or // not using modulo division operator if the output of // num%999 is equal to 0 then given number is divisible // by 999 otherwise not divisible by 999 if ($num % 999 == 0) { echo "Yes"; } else { echo "No"; } ?> |
Javascript
<script> // JavaScript code for the above approach //input let n = 235764 // finding given number is divisible by 999 or not if (n % 999 == 0) document.write("Yes") else document.write("No") // This code is contributed by Potta Lokesh </script> |
Output
Yes
Time Complexity : O(1)
Auxiliary Space: O(1)
Method 3: The function returns a Boolean value indicating whether the input integer is divisible by 999 or not. The function calculates this by checking if the sum of the digits of num is divisible by 9 and if the last three digits of num are divisible by 27. This code then tests the function with the examples: 999, 998 and 9987 and outputs the values True, False and False respectively.
C++
convert C++ code into Javascript code #include <bits/stdc++.h> using namespace std; bool is_divisible_by_999(int num) { string num_str = to_string(num); int sum = 0; for (char digit : num_str) { sum += digit - '0'; } return sum % 9 == 0 && stoi(num_str.substr(num_str.length() - 3)) % 27 == 0; } int main() { cout << is_divisible_by_999(999) << endl; // True cout << is_divisible_by_999(998) << endl; // False cout << is_divisible_by_999(9987) << endl; // False return 0; } |
Java
public class Main { public static boolean isDivisibleBy999(int num) { String numStr = String.valueOf(num); int sum = 0; for (int i = 0; i < numStr.length(); i++) { char digit = numStr.charAt(i); sum += Character.getNumericValue(digit); } return sum % 9 == 0 && Integer.parseInt(numStr.substring(numStr.length() - 3)) % 27 == 0; } public static void main(String[] args) { System.out.println(isDivisibleBy999(999)); // true System.out.println(isDivisibleBy999(998)); // false System.out.println(isDivisibleBy999(9987)); // false } } |
Python3
def is_divisible_by_999(num): num_str = str(num) return sum(int(digit) for digit in num_str) % 9 == 0 and int(num_str[-3:]) % 27 == 0 print(is_divisible_by_999(999)) # True print(is_divisible_by_999(998)) # False print(is_divisible_by_999(9987)) # False |
C#
using System; class Program { static bool IsDivisibleBy999(int num) { string numStr = num.ToString(); int digitSum = 0; foreach (char digitChar in numStr) { digitSum += digitChar - '0'; } return digitSum % 9 == 0 && int.Parse(numStr.Substring(numStr.Length - 3)) % 27 == 0; } static void Main() { Console.WriteLine(IsDivisibleBy999(999)); // True Console.WriteLine(IsDivisibleBy999(998)); // False Console.WriteLine(IsDivisibleBy999(9987)); // False } } |
Javascript
function is_divisible_by_999(num) { // Convert the input number to a string var num_str = num.toString(); // Initialize a variable to hold the sum of the digits var sum = 0; // Iterate over each character in the string representation of the number for (var i = 0; i < num_str.length; i++) { // Add the numeric value of the current digit to the sum variable sum += parseInt(num_str[i]); } // Check if the sum is divisible by 9 and the last three digits of the number are divisible by 27 return (sum % 9 == 0 && parseInt(num_str.substring(num_str.length - 3)) % 27 == 0); } // Test the function with some sample inputs console.log(is_divisible_by_999(999)); // true console.log(is_divisible_by_999(998)); // false console.log(is_divisible_by_999(9987)); // false // This code is contributed by bhardwajji. |
Output
True False False
Time complexity: O(1),
Auxiliary Space : O(1)
Method 4: Using string manipulation
1. Convert the number to a string.
2. Find the sum of every third digit from the right end to the left end.
3. If the sum is divisible by 3, then the original number is divisible by 999.
Java
public class GFG { public static boolean isDivisibleBy999(int n) { String s = Integer.toString(n); int l = s.length(); int sum = 0; for (int i = l - 1; i >= 0; i -= 3) { int j = Math.max(i - 2, -1); sum += Integer.parseInt(s.substring(j + 1, i + 1)); } return sum % 3 == 0; } public static void main(String[] args) { int n1 = 998; int n2 = 999; System.out.println(isDivisibleBy999(n1)); System.out.println(isDivisibleBy999(n2)); } } |
Python3
# python code to check if given number is divisible by 998 or not def is_divisible_by_999(n): s = str(n) l = len(s) sum = 0 for i in range(l-1, -1, -3): j = max(i-2, -1) sum += int(s[j+1:i+1]) return sum % 3 == 0 # Example usage n1 = 998n2 = 999print(is_divisible_by_999(n1)) # Output: True print(is_divisible_by_999(n2)) # Output: False |
C++
#include <iostream> #include <string> using namespace std; bool isDivisibleBy999(int n) { string s = to_string(n); int l = s.length(); int sum = 0; for (int i = l - 1; i >= 0; i -= 3) { int j = max(i - 2, -1); sum += stoi(s.substr(j + 1, i - j)); } return sum % 3 == 0; } int main() { int n1 = 998; int n2 = 999; cout << isDivisibleBy999(n1) << endl; cout << isDivisibleBy999(n2) << endl; return 0; } |
C#
using System; public class GFG { public static bool IsDivisibleBy999(int n) { string s = n.ToString(); int l = s.Length; int sum = 0; for (int i = l - 1; i >= 0; i -= 3) { int j = Math.Max(i - 2, -1); sum += int.Parse(s.Substring(j + 1, i - j)); } return sum % 3 == 0; } public static void Main(string[] args) { int n1 = 998; int n2 = 999; Console.WriteLine(IsDivisibleBy999(n1)); Console.WriteLine(IsDivisibleBy999(n2)); } } // This code is contributed by shiv1o43g |
Javascript
// JavaScript code to check if given number is divisible by 998 or not function isDivisibleBy998(n) { let s = n.toString(); let l = s.length; let sum = 0; for (let i = l - 1; i >= 0; i -= 3) { let j = Math.max(i - 2, -1); sum += parseInt(s.substring(j + 1, i + 1)); } return sum % 3 === 0; } // Example usage let n1 = 998; let n2 = 999; console.log(isDivisibleBy998(n1)); console.log(isDivisibleBy998(n2)); |
Output
False True
The time complexity of the given function is_divisible_by_999 is O(N/3) where N is the number of digits in the input number n. This is because the loop iterates over every third digit of the input number, and performs constant time operations (such as string slicing and integer conversion) on each iteration.
The auxiliary space used by the function is O(1), since it uses a constant amount of extra space to store the loop variables and the running sum.
More Divisibility Algorithms.
This article is contributed by Shivam Pradhan (anuj_charm). If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
