Check if a number is divisible by 31 or not

Namachila 1 hour ago

0 0 4 minutes read

Given a number N, the task is to check whether the number is divisible by 31 or not.
Examples:

Input: N = 1922
Output: Yes
Explanation:
31 * 62 = 1922
Input: N = 2722400
Output: No

Approach: The divisibility test of 31 is:

Extract the last digit.
Subtract 3 * last digit from the remaining number obtained after removing the last digit.
Repeat the above steps until a two-digit number, or zero, is obtained.
If the two-digit number is divisible by 31, or it is 0, then the original number is also divisible by 31.

For example:

If N = 49507

Step 1:
  N = 49507
  Last digit = 7
  Remaining number = 4950
  Subtracting 3 times last digit
  Resultant number = 4950 - 3*7 = 4929

Step 2:
  N = 4929
  Last digit = 9
  Remaining number = 492
  Subtracting 3 times last digit
  Resultant number = 492 - 3*9 = 465

Step 3:
  N = 465
  Last digit = 5
  Remaining number = 46
  Subtracting 3 times last digit
  Resultant number = 46 - 3*5 = 31

Step 4:
  N = 31
  Since N is a two-digit number,
  and 31 is divisible by 31

Therefore N = 49507 is also divisible by 31

Below is the implementation of the above approach:

C++

// C++ program to check whether a number
// is divisible by 31 or not
#include<bits/stdc++.h>
#include<stdlib.h>
 
using namespace std;
 
// Function to check if the number is divisible by 31 or not 
bool isDivisible(int n) 
{
    int d;
     
    // While there are at least two digits 
    while (n / 100) 
    {
 
        // Extracting the last 
        d = n % 10;
 
        // Truncating the number 
        n /= 10;
 
        // Subtracting three times the last 
        // digit to the remaining number 
        n = abs(n-(d * 3));
    }
     
    // Finally return if the two-digit
    // number is divisible by 31 or not
    return (n % 31 == 0) ;
}
 
// Driver Code 
int main() 
{
    int N = 1922;
 
    if (isDivisible(N)) 
        cout<<"Yes"<<endl ;
    else
        cout<<"No"<<endl ;
     
    return 0;     
} 
 
// This code is contributed by ANKITKUMAR34

Java

// Java program to check whether a number
// is divisible by 31 or not
import java.util.*;
 
class GFG{
  
// Function to check if the number is divisible by 31 or not 
static boolean isDivisible(int n) 
{
    int d;
      
    // While there are at least two digits 
    while ((n / 100) > 0) 
    {
  
        // Extracting the last 
        d = n % 10;
  
        // Truncating the number 
        n /= 10;
  
        // Subtracting three times the last 
        // digit to the remaining number 
        n = Math.abs(n - (d * 3));
    }
      
    // Finally return if the two-digit
    // number is divisible by 31 or not
    return (n % 31 == 0) ;
}
  
// Driver Code 
public static void main(String[] args) 
{
    int N = 1922;
  
    if (isDivisible(N)) 
        System.out.print("Yes");
    else
        System.out.print("No");
}     
} 
 
// This code is contributed by PrinciRaj1992

Python 3

# Python program to check whether a number
# is divisible by 31 or not
 
# Function to check if the number is 
# divisible by 31 or not 
def isDivisible(n) : 
 
    # While there are at least two digits 
    while n // 100 : 
 
        # Extracting the last 
        d = n % 10
 
        # Truncating the number 
        n //= 10
 
        # Subtracting three times the last 
        # digit to the remaining number 
        n = abs(n-(d * 3))
 
    # Finally return if the two-digit
    # number is divisible by 31 or not
    return (n % 31 == 0) 
 
# Driver Code 
if __name__ == "__main__" : 
 
    n = 1922
 
    if (isDivisible(n)) : 
        print("Yes") 
    else : 
        print("No") 

C#

// C# program to check whether a number
// is divisible by 31 or not
using System;
 
class GFG{
   
// Function to check if the number is divisible by 31 or not 
static bool isDivisible(int n) 
{
    int d;
       
    // While there are at least two digits 
    while ((n / 100) > 0) 
    {
   
        // Extracting the last 
        d = n % 10;
   
        // Truncating the number 
        n /= 10;
   
        // Subtracting three times the last 
        // digit to the remaining number 
        n = Math.Abs(n - (d * 3));
    }
       
    // Finally return if the two-digit
    // number is divisible by 31 or not
    return (n % 31 == 0) ;
}
   
// Driver Code 
public static void Main(String[] args) 
{
    int N = 1922;
   
    if (isDivisible(N)) 
        Console.Write("Yes");
    else
        Console.Write("No");
}     
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
// Javascript program to check whether a number
// is divisible by 31 or not
   
// Function to check if the number is divisible by 31 or not 
function isDivisible(n) 
{
    let d;
        
    // While there are at least two digits 
    while (Math.floor(n / 100) > 0) 
    {
    
        // Extracting the last 
        d = n % 10;
    
        // Truncating the number 
        n = Math.floor(n / 10);
    
        // Subtracting three times the last 
        // digit to the remaining number 
        n = Math.abs(n - (d * 3));
    }
        
    // Finally return if the two-digit
    // number is divisible by 31 or not
    return (n % 31 == 0) ;
}
 
// Driver Code
     
    let N = 1922;
     
    if (isDivisible(N) != 0) 
        document.write("Yes") ;
    else
        document.write("No");
 
// This code is contributed by sanjoy_62.
</script>

Output:

Yes

Time Complexity: O(log₁₀N)

Auxiliary Space: O(1)

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 zambiatek!