Given a number N, the task is to check whether the number is divisible by 47 or not.
Examples:
Input: N = 1645
Output: yes
Explanation:
47 * 35 = 1645
Input: N = 4606
Output: yes
Explanation:
47 * 98 = 4606
Approach: The divisibility test of 47 is:
- Extract the last digit.
- Subtract 14 * 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 47, or it is 0, then the original number is also divisible by 47.
For example:
If N = 59173 Step 1: N = 59173 Last digit = 3 Remaining number = 5917 Subtracting 14 times last digit Resultant number = 5917 - 14*3 = 5875 Step 2: N = 5875 Last digit = 5 Remaining number = 587 Subtracting 14 times last digit Resultant number = 587 - 14*5 = 517 Step 3: N = 517 Last digit = 7 Remaining number = 51 Subtracting 14 times last digit Resultant number = 51 - 14*7 = -47 Step 4: N = -47 Since N is a two-digit number, and -47 is divisible by 47 Therefore N = 59173 is also divisible by 47
Below is the implementation of the above approach:
C++
// C++ program to check whether a number // is divisible by 47 or not #include<bits/stdc++.h> #include<stdlib.h> using namespace std; // Function to check if the number is divisible by 47 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 fourteen times the last // digit to the remaining number n = abs (n-(d * 14)); } // Finally return if the two-digit // number is divisible by 47 or not return (n % 47 == 0) ; } // Driver Code int main() { int N = 59173; 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 47 or not import java.util.*; class GFG{ // Function to check if the number is divisible by 47 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 fourteen times the last // digit to the remaining number n = Math.abs(n - (d * 14 )); } // Finally return if the two-digit // number is divisible by 47 or not return (n % 47 == 0 ) ; } // Driver Code public static void main(String[] args) { int N = 59173 ; if (isDivisible(N)) System.out.print( "Yes" ) ; else System.out.print( "No" ); } } // This code is contributed by PrinciRaj1992 |
Python 3
# Python program to check if a number # is divisible by 47 or not # Function to check if the number is # divisible by 47 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 fourteen times the last # digit to the remaining number n = abs (n - (d * 14 )) # Finally return if the two-digit # number is divisible by 43 or not return (n % 47 = = 0 ) # Driver Code if __name__ = = "__main__" : n = 59173 if (isDivisible(n)) : print ( "Yes" ) else : print ( "No" ) |
C#
// C# program to check whether a number // is divisible by 47 or not using System; class GFG { // Function to check if the number is divisible by 47 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 fourteen times the last // digit to the remaining number n = Math.Abs(n - (d * 14)); } // Finally return if the two-digit // number is divisible by 47 or not return (n % 47 == 0); } // Driver Code public static void Main() { int N = 59173; if (isDivisible(N)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by mohit kumar 29. |
Javascript
<script> // Javascript program to check whether a number // is divisible by 47 or not // Function to check if the number is divisible by 47 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 fourteen times the last // digit to the remaining number n = Math.abs(n - (d * 14)); } // Finally return if the two-digit // number is divisible by 47 or not return (n % 47 == 0) ; } // Driver Code let N = 59173; if (isDivisible(N) != 0) document.write( "Yes" ) ; else document.write( "No" ); // This code is contributed by sanjoy_62. </script> |
PHP
<?php // PHP program to check whether a number // is divisible by 47 or not // Function to check if the number is divisible by 47 or not function isDivisible( $n ) { // While there are at least two digits while (( $n / 100) <=0) { // Extracting the last $d = $n % 10; // Truncating the number $n = ( $n /10); // Subtracting seven times the last // digit to the remaining number $n = Math. abs ( $n - ( $d * 14)); } // Finally return if the two-digit // number is divisible by 71 or not return ( $n % 47 == 0) ; } // Driver Code $N = 1645; if (isDivisible( $N )) { echo ( "Yes" ) ; } else { echo ( "No" ); } // This code is contributed by ksrikanth0498 ?> |
Output:
Yes
Time Complexity: O(log10N)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!