Check the divisibility of Hexadecimal numbers

0 0 8 minutes read

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) = 0

Input: 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 m
bool 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 code
int main()
{
    string s = "10";
    int m = 4;
 
    if (isDivisible(s, m))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

Java

// Java code implementation of above approach
import 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 code
 
 
def 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 approach
using 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 m
function 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 code
const 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 m
bool 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 code
int main()
{
    string s = "10";
    int m = 4;
 
    if (isDivisible(s, m))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG 
{
 
static char []CHARS = "0123456789ABCDEF".toCharArray();
static int DIGITS = 16;
 
// Function that returns true
// if s is divisible by m
static 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 code
public 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 approach
CHARS = "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 approach
using 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 m
static 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 code
public 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 approach
 
var CHARS = "0123456789ABCDEF";
var DIGITS = 16;
 
// Function that returns true
// if s is divisible by m
function 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 code
var 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 zambiatek!