Comprobar la divisibilidad de los números hexadecimales

Dada una string S que consta de un gran número hexadecimal, la tarea es verificar su divisibilidad por un número decimal M dado . Si es divisible, imprima Sí ; de lo contrario, imprima No.
Ejemplos: 
 

Entrada: S = “10”, M = 4 
Salida: Sí 
10 es 16 en decimal y (16 % 4) = 0
Entrada: S = “10”, M = 5 
Salida: No 
 

Enfoque: se utilizará un enfoque utilizado en este artículo para evitar el desbordamiento. Iterar toda la string desde la parte posterior. 
Si el resto de la substring S[0…i] se conoce en la división con M . Llamemos a este resto como R . Esto se puede usar para obtener el resto cuando se divide la substring S[0…i+1] . Para hacer eso, primero desplace a la izquierda la string S[0…i] por 1 . Esto será equivalente a multiplicar la string por 16 . Luego, agregue S[i+1] a esto y tome su mod con M . Con un poco de aritmética modular se reduce a 
 

S[0…i+1] % M = (S[0…i] * 16 + S[i+1]) % M = ((S[0…i] % M * 16) + S[i+1 ]) % H 
 

Por lo tanto, continúe con los pasos anteriores hasta el final de la string. Si el residuo final es 0 , entonces la string es divisible, de lo contrario no lo es.
A continuación se muestra la implementación del enfoque anterior: 
 

// 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 = 3;
 
    if (isDivisible(s, m))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

// 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 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# 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

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

Complejidad temporal: O(n)

Espacio auxiliar: O (logn)