Given a very large number in the form of a string, the task is to check if the number is divisible by 75 or not.
Examples:
Input: N = 175 Output: No Input: N = 100000000000000000754586672150 Output: Yes
Approach 1: A number is divisible by 75 only if it is divisible by 3(if the sum of the digit is divisible by 3) and divisible by 25 (if the last two digits is divisible by 25) both.
Below is the implementation to check whether the given number is divisible by 75 or not.
C++
// C++ implementation to check the number// is divisible by 75 or not#include <bits/stdc++.h>using namespace std;// check divisibleBy3bool divisibleBy3(string number){ // to store sum of Digit int sumOfDigit = 0; // traversing through each digit for (int i = 0; i < number.length(); i++) // summing up Digit sumOfDigit += number[i] - '0'; // check if sumOfDigit is divisibleBy3 if (sumOfDigit % 3 == 0) return true; return false;}// check divisibleBy25bool divisibleBy25(string number){ // if a single digit number if (number.length() < 2) return false; // length of the number int length = number.length(); // taking the last two digit int lastTwo = (number[length - 2] - '0') * 10 + (number[length - 1] - '0'); // checking if the lastTwo digit is divisibleBy25 if (lastTwo % 25 == 0) return true; return false;}// Function to check divisibleBy75 or notbool divisibleBy75(string number){ // check if divisibleBy3 and divisibleBy25 if (divisibleBy3(number) && divisibleBy25(number)) return true; return false;}// Drivers codeint main(){ string number = "754586672150"; // divisible bool divisible = divisibleBy75(number); // if divisibleBy75 if (divisible) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation to check the number// is divisible by 75 or notimport java.io.*;class GFG {// check divisibleBy3static boolean divisibleBy3(String number){ // to store sum of Digit int sumOfDigit = 0; // traversing through each digit for (int i = 0; i < number.length(); i++) // summing up Digit sumOfDigit += number.charAt(i) - '0'; // check if sumOfDigit is divisibleBy3 if (sumOfDigit % 3 == 0) return true; return false;}// check divisibleBy25static boolean divisibleBy25(String number){ // if a single digit number if (number.length() < 2) return false; // length of the number int length = number.length(); // taking the last two digit int lastTwo = (number.charAt(length - 2) - '0') * 10 + (number.charAt(length - 1) - '0'); // checking if the lastTwo digit is divisibleBy25 if (lastTwo % 25 == 0) return true; return false;}// Function to check divisibleBy75 or notstatic boolean divisibleBy75(String number){ // check if divisibleBy3 and divisibleBy25 if (divisibleBy3(number) && divisibleBy25(number)) return true; return false;}// Drivers code public static void main (String[] args) { String number = "754586672150"; // divisible boolean divisible = divisibleBy75(number); // if divisibleBy75 if (divisible) System.out.println( "Yes"); else System.out.println( "No"); }}// This code is contributed // by inder_verma.. |
Python3
# Python 3 implementation to check the # number is divisible by 75 or not# check divisibleBy3def divisibleBy3(number): # to store sum of Digit sumOfDigit = 0 # traversing through each digit for i in range(0, len(number), 1): # summing up Digit sumOfDigit += ord(number[i]) - ord('0') # check if sumOfDigit is divisibleBy3 if (sumOfDigit % 3 == 0): return True return False# check divisibleBy25def divisibleBy25(number): # if a single digit number if (len(number) < 2): return False # length of the number length = len(number) # taking the last two digit lastTwo = ((ord(number[length - 2]) - ord('0')) * 10 + (ord(number[length - 1]) - ord('0'))) # checking if the lastTwo digit # is divisibleBy25 if (lastTwo % 25 == 0): return True return False# Function to check divisibleBy75 or notdef divisibleBy75(number): # check if divisibleBy3 and divisibleBy25 if (divisibleBy3(number) and divisibleBy25(number)): return True return False# Driver Codeif __name__ == '__main__': number = "754586672150" # divisible divisible = divisibleBy75(number) # if divisibleBy75 if (divisible): print("Yes") else: print("No")# This code is contributed by # Surendra_Gangwar |
C#
// C# implementation to check the number// is divisible by 75 or notusing System;class GFG {// check divisibleBy3static bool divisibleBy3(string number){ // to store sum of Digit int sumOfDigit = 0; // traversing through each digit for (int i = 0; i < number.Length; i++) // summing up Digit sumOfDigit += number[i] - '0'; // check if sumOfDigit is divisibleBy3 if (sumOfDigit % 3 == 0) return true; return false;}// check divisibleBy25static bool divisibleBy25(string number){ // if a single digit number if (number.Length < 2) return false; // length of the number int length = number.Length; // taking the last two digit int lastTwo = (number[length - 2] - '0') * 10 + (number[length - 1] - '0'); // checking if the lastTwo digit // is divisibleBy25 if (lastTwo % 25 == 0) return true; return false;}// Function to check divisibleBy75 or notstatic bool divisibleBy75(string number){ // check if divisibleBy3 and divisibleBy25 if (divisibleBy3(number) && divisibleBy25(number)) return true; return false;}// Driver Codepublic static void Main () { string number = "754586672150"; // divisible bool divisible = divisibleBy75(number); // if divisibleBy75 if (divisible) Console.WriteLine( "Yes"); else Console.WriteLine( "No");}}// This code is contributed // by inder_verma.. |
PHP
<?php// PHP implementation to check the // number is divisible by 75 or not// check divisibleBy3function divisibleBy3($number){ // to store sum of Digit $sumOfDigit = 0; // traversing through each digit for ($i = 0; $i < strlen($number); $i++) // summing up Digit $sumOfDigit += $number[$i] - '0'; // check if sumOfDigit is // divisibleBy3 if ($sumOfDigit % 3 == 0) return true; return false;}// check divisibleBy25function divisibleBy25($number){ // if a single digit number if (strlen($number) < 2) return false; // length of the number $length = strlen($number); // taking the last two digit $lastTwo = ($number[$length - 2] - '0') * 10 + ($number[$length - 1] - '0'); // checking if the lastTwo digit // is divisibleBy25 if ($lastTwo % 25 == 0) return true; return false;}// Function to check divisibleBy75 or notfunction divisibleBy75($number){ // check if divisibleBy3 and // divisibleBy25 if (divisibleBy3($number) && divisibleBy25($number)) return true; return false;}// Driver Code$number = "754586672150";// divisible$divisible = divisibleBy75($number);// if divisibleBy75if ($divisible) echo "Yes";else echo "No"; // This code is contributed by ANKITRAI1?> |
Javascript
<script>// JavaScript implementation to check the number// is divisible by 75 or not// check divisibleBy3function divisibleBy3(number){ // to store sum of Digit let sumOfDigit = 0; // traversing through each digit for (let i = 0; i < number.length; i++) // summing up Digit sumOfDigit += number[i] - '0'; // check if sumOfDigit is divisibleBy3 if (sumOfDigit % 3 == 0) return true; return false;}// check divisibleBy25function divisibleBy25(number){ // if a single digit number if (number.length < 2) return false; // length of the number let length = number.length; // taking the last two digit let lastTwo = (number[length - 2] - '0') * 10 + (number[length - 1] - '0'); // checking if the lastTwo digit is divisibleBy25 if (lastTwo % 25 == 0) return true; return false;}// Function to check divisibleBy75 or notfunction divisibleBy75(number){ // check if divisibleBy3 and divisibleBy25 if (divisibleBy3(number) && divisibleBy25(number)) return true; return false;}// Drivers code let number = "754586672150"; // divisible let divisible = divisibleBy75(number); // if divisibleBy75 if (divisible) document.write("Yes"); else document.write("No");</script> |
Output
No
Time Complexity: O(length(number))
Auxiliary Space: O(1)
Approach 2: Using Sum of Digits Method
Here is steps to this approach:
- In this implementation, we first check if the number has at least two digits, because any number less than 75 can’t be divisible by 75.
- Then, we calculate the last two digits of the number and check if they are divisible by 25. If not, the number can’t be divisible by 75.
- Next, we calculate the sum of all the digits of the number and check if it is divisible by 3. If not, the number can’t be divisible by 75. Finally, if both conditions are satisfied, the number is divisible by 75.
Here is the code below:
C++
#include <bits/stdc++.h>using namespace std;bool isDivisibleBy75(string number) { int n = number.length(); // if number is less than 75, it can't be divisible by 75 if (n < 2) { return false; } // calculate the last two digits of the number int lastTwoDigits = (number[n-2]-'0')*10 + (number[n-1]-'0'); // if last two digits are not divisible by 25, the number can't be divisible by 75 if (lastTwoDigits % 25 != 0) { return false; } // calculate the sum of all the digits int sumOfDigits = 0; for (int i = 0; i < n; i++) { sumOfDigits += number[i]-'0'; } // if sum of digits is not divisible by 3, the number can't be divisible by 75 if (sumOfDigits % 3 != 0) { return false; } // if all conditions are satisfied, the number is divisible by 75 return true;}int main() { string number = "754586672150"; if (isDivisibleBy75(number)) { cout << "Yes\n"; } else { cout << "No\n"; } return 0;} |
Java
// Java program for the above approachimport java.util.Scanner;public class Main { public static void main(String[] args) { String number = "754586672150"; if (isDivisibleBy75(number)) { System.out.println("Yes"); } else { System.out.println("No"); } } private static boolean isDivisibleBy75(String number) { int n = number.length(); // if number is less than 75, it can't be divisible by 75 if (n < 2) { return false; } // calculate the last two digits of the number int lastTwoDigits = (number.charAt(n - 2) - '0') * 10 + (number.charAt(n - 1) - '0'); // if last two digits are not divisible by 25, the number can't be divisible by 75 if (lastTwoDigits % 25 != 0) { return false; } // calculate the sum of all the digits int sumOfDigits = 0; for (int i = 0; i < n; i++) { sumOfDigits += number.charAt(i) - '0'; } // if sum of digits is not divisible by 3, the number can't be divisible by 75 if (sumOfDigits % 3 != 0) { return false; } // if all conditions are satisfied, the number is divisible by 75 return true; }}// This code is contributed by rishabmalhdijo |
Python3
def isDivisibleBy75(number): n = len(number) # if number is less than 75, it can't be divisible by 75 if n < 2: return False # calculate the last two digits of the number lastTwoDigits = int(number[n-2:]) # if last two digits are not divisible by 25, the number can't be divisible by 75 if lastTwoDigits % 25 != 0: return False # calculate the sum of all the digits sumOfDigits = 0 for digit in number: sumOfDigits += int(digit) # if sum of digits is not divisible by 3, the number can't be divisible by 75 if sumOfDigits % 3 != 0: return False # if all conditions are satisfied, the number is divisible by 75 return True# Driver codenumber = "754586672150"if isDivisibleBy75(number): print("Yes")else: print("No") |
C#
using System;public class MainClass{ private static bool IsDivisibleBy75(string number) { int n = number.Length; // if number is less than 75, it can't be divisible by 75 if (n < 2) { return false; } // calculate the last two digits of the number int lastTwoDigits = (number[n - 2] - '0') * 10 + (number[n - 1] - '0'); // if last two digits are not divisible by 25, the number can't be divisible by 75 if (lastTwoDigits % 25 != 0) { return false; } // calculate the sum of all the digits int sumOfDigits = 0; for (int i = 0; i < n; i++) { sumOfDigits += number[i] - '0'; } // if sum of digits is not divisible by 3, the number can't be divisible by 75 if (sumOfDigits % 3 != 0) { return false; } // if all conditions are satisfied, the number is divisible by 75 return true; } public static void Main(string[] args) { string number = "754586672150"; if (IsDivisibleBy75(number)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } }} |
Javascript
function isDivisibleBy75(number) { let n = number.length; // if number is less than 75, it can't be divisible by 75 if (n < 2) { return false; } // calculate the last two digits of the number let lastTwoDigits = (number[n-2]-'0')*10 + (number[n-1]-'0'); // if last two digits are not divisible by 25, the number can't be divisible by 75 if (lastTwoDigits % 25 != 0) { return false; } // calculate the sum of all the digits let sumOfDigits = 0; for (let i = 0; i < n; i++) { sumOfDigits += number[i]-'0'; } // if sum of digits is not divisible by 3, the number can't be divisible by 75 if (sumOfDigits % 3 != 0) { return false; } // if all conditions are satisfied, the number is divisible by 75 return true;}let number = "754586672150";if (isDivisibleBy75(number)) { console.log("Yes");} else { console.log("No");} |
Output
No
Time Complexity: O(N) where n is the length of the input string.
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!
