Check if a large number is divisible by 9 or not
Given a number, the task is to find if the number is divisible by 9 or not. The input number may be large and it may not be possible to store even if we use long long int.
Examples:
Input : n = 69354 Output : Yes Input : n = 234567876799333 Output : No Input : n = 3635883959606670431112222 Output : No
Since input number may be very large, we cannot use n % 9 to check if a number is divisible by 9 or not, especially in languages like C/C++. The idea is based on following fact.
A number is divisible by 9 if sum of its digits is divisible by 9.
Illustration:
For example n = 9432 Sum of digits = 9 + 4 + 3 + 2 = 18 Since sum is divisible by 9, answer is Yes.
How does this work?
Let us consider 1332, we can write it as 1332 = 1*1000 + 3*100 + 3*10 + 2 The proof is based on below observation: Remainder of 10i divided by 9 is 1 So powers of 10 only results in remainder 1 when divided by 9. Remainder of "1*1000 + 3*100 + 3*10 + 2" divided by 9 can be written as : 1*1 + 3*1 + 3*1 + 2 = 9 The above expression is basically sum of all digits. Since 9 is divisible by 9, answer is yes.
Below is the implementation of the above idea.
C++
// C++ program to find if a number is divisible by // 9 or not #include<bits/stdc++.h> using namespace std; // Function to find that number divisible by 9 or not int check(string str) { // Compute sum of digits int n = str.length(); int digitSum = 0; for ( int i=0; i<n; i++) digitSum += (str[i]- '0' ); // Check if sum of digits is divisible by 9. return (digitSum % 9 == 0); } // Driver code int main() { string str = "99333" ; check(str)? cout << "Yes" : cout << "No " ; return 0; } |
Java
// Java program to find if a number is // divisible by 9 or not import java.io.*; class IsDivisible { // Function to find that number // is divisible by 9 or not static boolean check(String str) { // Compute sum of digits int n = str.length(); int digitSum = 0 ; for ( int i= 0 ; i<n; i++) digitSum += (str.charAt(i)- '0' ); // Check if sum of digits is divisible by 9. return (digitSum % 9 == 0 ); } // main function public static void main (String[] args) { String str = "99333" ; if (check(str)) System.out.println( "Yes" ); else System.out.println( "No" ); } } |
Python3
# Python 3 program to # find if a number is # divisible by # 9 or not # Function to find that # number divisible by 9 # or not def check(st) : # Compute sum of digits n = len (st) digitSum = 0 for i in range ( 0 ,n) : digitSum = digitSum + ( int )(st[i]) # Check if sum of digits # is divisible by 9. return (digitSum % 9 = = 0 ) # Driver code st = "99333" if (check(st)) : print ( "Yes" ) else : print ( "No" ) # This code is contributed by Nikita Tiwari. |
C#
// C# program to find if a number is // divisible by 9 or not. using System; class GFG { // Function to find that number // is divisible by 9 or not static bool check(String str) { // Compute sum of digits int n = str.Length; int digitSum = 0; for ( int i = 0; i < n; i++) digitSum += (str[i] - '0' ); // Check if sum of digits is // divisible by 9. return (digitSum % 9 == 0); } // main function public static void Main () { String str = "99333" ; if (check(str)) Console.Write( "Yes" ); else Console.Write( "No" ); } } // This code is Contributed by // nitin mittal. |
PHP
<?php // PHP program to find if a number // is divisible by 9 or not // Function to find that // number divisible by 9 or not function check( $str ) { // Compute sum of digits $n = strlen ( $str ); $digitSum = 0; for ( $i = 0; $i < $n ; $i ++) $digitSum += ( $str [ $i ] - '0' ); // Check if sum of digits // is divisible by 9. return ( $digitSum % 9 == 0); } // Driver code $str = "99333" ; $x = check( $str ) ? "Yes" : "No " ; echo ( $x ); // This code is contributed by Ajit. ?> |
Javascript
<script> // Javascript program to find if a number // is divisible by 9 or not // Function to find that // number divisible by 9 or not function check(str) { // Compute sum of digits let n = str.length; let digitSum = 0; for (let i = 0; i < n; i++) digitSum += (str[i] - '0' ); // Check if sum of digits // is divisible by 9. return (digitSum % 9 == 0); } // Driver code let str = "99333" ; let x = check(str) ? "Yes" : "No " ; document.write(x); // This code is contributed by _saurabh_jaiswal. </script> |
Yes
Time Complexity: O(logN), as we are traversing the digits which will effectively costs logN time.
Auxiliary Space: O(1), as we are not using any extra space.
Method 2: Checking given number is divisible by 9 or not by using the modulo division operator “%”.
C++
#include <iostream> using namespace std; int main() { // input long long int n = 3635883959606670431112222; // finding given number is // divisible by 9 or not if (n % 9 == 0) { cout<< "Yes" ; } else { cout<< "No" ; } return 0; } // This code is contributed by laxmigangarajula03 |
Java
/*package whatever //do not write package name here */ // java program to check if given number is divisible by 9 or // not using modulo division import java.io.*; import java.math.BigInteger; class GFG { public static void main (String[] args) { // input number BigInteger n, b1,b2; n = new BigInteger( "3635883959606670431112222" ); b1 = new BigInteger( "9" ); // apply mod() method BigInteger result = n.mod(b1); // checking if the given number is divisible by 9 or not // using modulo division operator if the output of num%9 // is equal to 0 then given number is divisible by 9 // otherwise not divisible by 9 b2 = new BigInteger( "0" ); int comparevalue = result.compareTo(b2); if (comparevalue== 0 ) { System.out.println( "Yes" ); } else { System.out.println( "No" ); } } } // This code is contributed by satwik4409. |
Python3
# Python code # To check whether the given number is divisible by 9 or not #input n = 3635883959606670431112222 # the above input can also be given as n=input() -> taking input from user # finding given number is divisible by 9 or not if int (n) % 9 = = 0 : print ( "Yes" ) else : print ( "No" ) # this code is contributed by gangarajula laxmi |
C#
using System; public class GFG { static public void Main() { // input double n = 36358839596066; // finding given number is // divisible by 9 or not if (n % 9 == 0) { Console.Write( "Yes" ); } else { Console.Write( "No" ); } } } // This code is contributed by laxmigangarajula03 |
Javascript
<script> // JavaScript code for the above approach //input var n=3635883959606670431112222 // finding given number is divisible by 9 or not if (n%9==0) document.write( "Yes" ) else document.write( "No" ) // This code is contributed by Potta Lokesh </script> |
PHP
<?php // PHP program to check // if a large number is // divisible by 9. // Driver Code // input number $num = 3635883959606670431112222; // finding given number is divisible by 9 or not if ( $num % 9 == 0) echo " divisible" ; else echo "not divisible" ; ?> |
No
Time complexity: O(1) it is performing constant operations
Auxiliary space: O(1)
Contact Us