Given a string S consisting of a large hexadecimal number, the task is to check its divisibility by a given decimal number M. If divisible then print Yes else print No.
Examples:
Input: S = “10”, M = 4
Output: Yes
10 is 16 in decimal and (16 % 4) = 0Input: S = “10”, M = 5
Output: No
Approach 1: In this approach, we first convert the hexadecimal number to decimal using the algorithm to convert a number from one base to another. Then, we simply check if the decimal number is divisible by the given number M using the modulo operator.
Here are the steps of above approach:
- Convert the given hexadecimal number to a decimal number. To do this, initialize a decimal_num variable to 0 and a base variable to 1. Iterate over the hexadecimal number from right to left and convert each hexadecimal digit to its decimal equivalent. If a character is not a valid hexadecimal digit, return false. Multiply the decimal equivalent of each digit by the base and add it to decimal_num. Finally, multiply the base by 16.
- Check whether the decimal_num is divisible by m using the modulo operator. If the remainder is 0, return true, else return false.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function that returns true// if s is divisible by mbool isDivisible(string s, int m){ // Convert hexadecimal number to decimal int decimal_num = 0; int base = 1; int n = s.length(); for (int i = n - 1; i >= 0; i--) { int digit; if (s[i] >= '0' && s[i] <= '9') { digit = s[i] - '0'; } else if (s[i] >= 'A' && s[i] <= 'F') { digit = s[i] - 'A' + 10; } else { // Invalid character in hexadecimal number return false; } decimal_num += digit * base; base *= 16; } // Check if decimal_num is divisible by m return decimal_num % m == 0;}// Driver codeint main(){ string s = "10"; int m = 4; if (isDivisible(s, m)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java code implementation of above approachimport java.util.*;public class Main { // Function that returns true // if s is divisible by m public static boolean isDivisible(String s, int m) { // Convert hexadecimal number to decimal int decimal_num = 0; int base = 1; int n = s.length(); for (int i = n - 1; i >= 0; i--) { int digit; if (s.charAt(i) >= '0' && s.charAt(i) <= '9') { digit = s.charAt(i) - '0'; } else if (s.charAt(i) >= 'A' && s.charAt(i) <= 'F') { digit = s.charAt(i) - 'A' + 10; } else { // Invalid character in hexadecimal number return false; } decimal_num += digit * base; base *= 16; } // Check if decimal_num is divisible by m return decimal_num % m == 0; } // Driver code public static void main(String[] args) { String s = "10"; int m = 4; if (isDivisible(s, m)) System.out.println("Yes"); else System.out.println("No"); }} |
Python
def is_divisible(s, m): # Convert hexadecimal number to decimal decimal_num = 0 base = 1 n = len(s) for i in range(n - 1, -1, -1): digit = 0 if '0' <= s[i] <= '9': digit = ord(s[i]) - ord('0') elif 'A' <= s[i] <= 'F': digit = ord(s[i]) - ord('A') + 10 else: # Invalid character in hexadecimal number return False decimal_num += digit * base base *= 16 # Check if decimal_num is divisible by m return decimal_num % m == 0# Driver codedef main(): s = "10" m = 4 if is_divisible(s, m): print("Yes") else: print("No")if __name__ == "__main__": main() |
C#
// C# code implementation of above approachusing System;public class GFG { // Function that returns true // if s is divisible by m public static bool IsDivisible(string s, int m) { // Convert hexadecimal number to decimal int decimalNum = 0; int baseValue = 1; int n = s.Length; for (int i = n - 1; i >= 0; i--) { int digit; if (s[i] >= '0' && s[i] <= '9') { digit = s[i] - '0'; } else if (s[i] >= 'A' && s[i] <= 'F') { digit = s[i] - 'A' + 10; } else { // Invalid character in hexadecimal number return false; } decimalNum += digit * baseValue; baseValue *= 16; } // Check if decimalNum is divisible by m return decimalNum % m == 0; } // Driver code public static void Main() { string s = "10"; int m = 4; if (IsDivisible(s, m)) Console.WriteLine("Yes"); else Console.WriteLine("No"); }} |
Javascript
// Function that returns true// if s is divisible by mfunction isDivisible(s, m) { // Convert hexadecimal number to decimal let decimalNum = 0; let base = 1; let n = s.length; for (let i = n - 1; i >= 0; i--) { let digit; if (s[i] >= '0' && s[i] <= '9') { digit = parseInt(s[i]); } else if (s[i] >= 'A' && s[i] <= 'F') { digit = s[i].charCodeAt(0) - 'A'.charCodeAt(0) + 10; } else { // Invalid character in hexadecimal number return false; } decimalNum += digit * base; base *= 16; } // Check if decimalNum is divisible by m return decimalNum % m === 0;}// Driver codeconst s = "10";const m = 4;if (isDivisible(s, m)) { console.log("Yes");} else { console.log("No");} |
Output
Yes
Time Complexity: O(n), where n is the length of the input string.
Auxiliary Space: O(1)
Approach 2: An approach used in this article will be used to avoid overflow. Iterate the entire string from the back-side.
If the remainder of the sub-string S[0…i] is known on division with M. Let’s call this remainder as R. This can be used to get the remainder when the substring S[0…i+1] is divided. To do that, first left shift the string S[0…i] by 1. This will be equivalent to multiplying the string by 16. Then, add S[i+1] to this and take its mod with M. With a little bit of modular arithmetic it boils down to
S[0…i+1] % M = (S[0…i] * 16 + S[i+1]) % M = ((S[0…i] % M * 16) + S[i+1]) % M
Thus, continue the above steps till the end of the string. If the final remainder is 0 then the string is divisible otherwise it is not.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;const string CHARS = "0123456789ABCDEF";const int DIGITS = 16;// Function that returns true// if s is divisible by mbool isDivisible(string s, int m){ // Map to map characters to real values unordered_map<char, int> mp; for (int i = 0; i < DIGITS; i++) { mp[CHARS[i]] = i; } // To store the remainder at any stage int r = 0; // Find the remainder for (int i = 0; i < s.size(); i++) { r = (r * 16 + mp[s[i]]) % m; } // Check the value of remainder if (!r) return true; return false;}// Driver codeint main(){ string s = "10"; int m = 4; if (isDivisible(s, m)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG {static char []CHARS = "0123456789ABCDEF".toCharArray();static int DIGITS = 16;// Function that returns true// if s is divisible by mstatic boolean isDivisible(String s, int m){ // Map to map characters to real values Map<Character, Integer> mp = new HashMap<>(); for (int i = 0; i < DIGITS; i++) { mp. put(CHARS[i], i); } // To store the remainder at any stage int r = 0; // Find the remainder for (int i = 0; i < s.length(); i++) { r = (r * 16 + mp.get(s.charAt(i))) % m; } // Check the value of remainder if (r == 0) return true; return false;}// Driver codepublic static void main(String []args) { String s = "10"; int m = 3; if (isDivisible(s, m)) System.out.println("Yes"); else System.out.println("No");}}// This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the approachCHARS = "0123456789ABCDEF"; DIGITS = 16; # Function that returns true # if s is divisible by m def isDivisible(s, m) : # Map to map characters to real value mp = dict.fromkeys(CHARS, 0); for i in range( DIGITS) : mp[CHARS[i]] = i; # To store the remainder at any stage r = 0; # Find the remainder for i in range(len(s)) : r = (r * 16 + mp[s[i]]) % m; # Check the value of remainder if (not r) : return True; return False; # Driver code if __name__ == "__main__" : s = "10"; m = 3; if (isDivisible(s, m)) : print("Yes"); else : print("No"); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG{static char []CHARS = "0123456789ABCDEF".ToCharArray();static int DIGITS = 16;// Function that returns true// if s is divisible by mstatic bool isDivisible(String s, int m){ // Map to map characters to real values Dictionary<char, int> mp = new Dictionary<char, int>(); for (int i = 0; i < DIGITS; i++) { if(mp.ContainsKey(CHARS[i])) mp[CHARS[i]] = i; else mp.Add(CHARS[i], i); } // To store the remainder at any stage int r = 0; // Find the remainder for (int i = 0; i < s.Length; i++) { r = (r * 16 + mp[s[i]]) % m; } // Check the value of remainder if (r == 0) return true; return false;}// Driver codepublic static void Main(String []args) { String s = "10"; int m = 3; if (isDivisible(s, m)) Console.WriteLine("Yes"); else Console.WriteLine("No");}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approachvar CHARS = "0123456789ABCDEF";var DIGITS = 16;// Function that returns true// if s is divisible by mfunction isDivisible(s, m){ // Map to map characters to real values var mp = new Map(); for (var i = 0; i < DIGITS; i++) { mp.set(CHARS[i], i); } // To store the remainder at any stage var r = 0; // Find the remainder for (var i = 0; i < s.length; i++) { r = (r * 16 + mp.get(s[i])) % m; } // Check the value of remainder if (!r) return true; return false;}// Driver codevar s = "10";var m = 3;if (isDivisible(s, m)) document.write( "Yes");else document.write( "No");</script> |
Output
Yes
Time complexity: O(n)
Auxiliary Space: O(log(n))
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!
