Modulus of two Hexadecimal Numbers

0 0 5 minutes read

Given two hexadecimal numbers N and K, the task is to find N modulo K.

Examples:

Input: N = 3E8, K = 13
Output: C
Explanation:
Decimal representation of N( = 3E8) is 1000
Decimal representation of K( = 13) is 19
Decimal representation of (N % K) = 1000 % 19 = 12 ( = C).
Therefore, the required output is C.

Input: N = 2A3, K = 1A
Output: 19

Approach: Follow the steps below to solve the problem:

Convert the hexadecimal numbers, N and K into their equivalent decimal numbers say, X and Y respectively.
Convert the decimal number, (X % Y) into its equivalent hexadecimal numbers say, res
Finally, print the value of res.

Below is the implementation of the above approach:

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate modulus of
// two Hexadecimal numbers
void hexaModK(string s, string k)
{
     
    // Store all possible
    // hexadecimal digits
    map<char, int> mp;
     
    // Iterate over the range ['0', '9']
    for(char i = 1; i <= 9; i++) 
    {
        mp[i + '0'] = i;
    }
     
    mp['A'] = 10;
    mp['B'] = 11;
    mp['C'] = 12;
    mp['D'] = 13;
    mp['E'] = 14;
    mp['F'] = 15;
     
    // Convert given string to long
    long m = stoi(k, 0, 16);
     
    // Base to get 16 power
    long base = 1;
     
    // Store N % K
    long ans = 0;
     
    // Iterate over the digits of N
    for(int i = s.length() - 1;
            i >= 0; i--) 
    {
         
        // Stores i-th digit of N
        long n = mp[s[i]] % m;
         
        // Update ans
        ans = (ans + (base % m * n
                      % m) % m) % m;
         
        // Update base
        base = (base % m * 16 % m) % m;
    }
     
    // Print the answer converting
    // into hexadecimal
    stringstream ss; 
    ss << hex << ans;
    string su = ss.str();
    transform(su.begin(), su.end(), 
              su.begin(), ::toupper); 
    cout << (su);
}
 
// Driver Code
int main() 
{
     
    // Given string N and K
    string n = "3E8";
    string k = "13";
     
    // Function Call
    hexaModK(n, k);
    return 0;
}
 
// This code is contributed by sallagondaavinashreddy7

Java

// Java program to implement 
// the above approach 
 
import java.util.*; 
public class Main { 
 
    // Function to calculate modulus of 
    // two Hexadecimal numbers 
    static void hexaModK(String N, String k) 
    { 
        // Store all possible 
        // hexadecimal digits 
        HashMap<Character, Integer> map 
            = new HashMap<>(); 
 
        // Iterate over the range ['0', '9'] 
        for (char i = '0'; i <= '9'; i++) { 
            map.put(i, i - '0'); 
        } 
        map.put('A', 10); 
        map.put('B', 11); 
        map.put('C', 12); 
        map.put('D', 13); 
        map.put('E', 14); 
        map.put('F', 15); 
 
        // Convert given string to long 
        long m = Long.parseLong(k, 16); 
 
        // Base to get 16 power 
        long base = 1; 
 
        // Store N % K 
        long ans = 0; 
 
        // Iterate over the digits of N 
        for (int i = N.length() - 1; 
            i >= 0; i--) { 
 
            // Stores i-th digit of N 
            long n 
                = map.get(N.charAt(i)) % m; 
 
            // Update ans 
            ans = (ans + (base % m * n % m) % m) % m; 
 
            // Update base 
            base = (base % m * 16 % m) % m; 
        } 
 
        // Print the answer converting 
        // into hexadecimal 
        System.out.println( 
            Long.toHexString(ans).toUpperCase()); 
    } 
 
    // Driver Code 
    public static void main(String args[]) 
    { 
        // Given string N and K 
        String n = "3E8"; 
        String k = "13"; 
 
        // Function Call 
        hexaModK(n, k); 
    } 
} 

Python3

# Python3 program to implement
# the above approach
 
# Function to calculate modulus of
# two Hexadecimal numbers
def hexaModK(s, k) :
     
    # Store all possible
    # hexadecimal digits
    mp = {};
     
    # Iterate over the range ['0', '9']
    for i in range(1, 10) : 
     
        mp[chr(i + ord('0'))] = i;
         
    mp['A'] = 10;
    mp['B'] = 11;
    mp['C'] = 12;
    mp['D'] = 13;
    mp['E'] = 14;
    mp['F'] = 15;
     
    # Convert given string to long
    m = int(k);
     
    # Base to get 16 power
    base = 1;
     
    # Store N % K
    ans = 0;
     
    # Iterate over the digits of N
    for i in range(len(s) - 1, -1, -1) :
         
        # Stores i-th digit of N
        n = mp[s[i]] % m;
         
        # Update ans
        ans = (ans + (base % m * n
                      % m) % m) % m;
         
        # Update base
        base = (base % m * 16 % m) % m;
     
    # Print the answer converting
    # into hexadecimal
    ans = hex(int(ans))[-1].upper()
     
    print(ans)
 
# Driver Code
if __name__ == "__main__" : 
     
    # Given string N and K
    n = "3E8";
    k = "13";
     
    # Function Call
    hexaModK(n, k);
 
    # This code is contributed by AnkThon

C#

// C# program to implement 
// the above approach 
using System;
using System.Collections.Generic;
  
class GFG{ 
 
// Function to calculate modulus of 
// two Hexadecimal numbers 
static void hexaModK(String N, String k) 
{ 
     
    // Store all possible 
    // hexadecimal digits 
    Dictionary<char,
               int> map = new Dictionary<char,
                                         int>(); 
 
    // Iterate over the range ['0', '9'] 
    for(char i = '0'; i <= '9'; i++)
    {
        map.Add(i, i - '0'); 
    } 
    map.Add('A', 10); 
    map.Add('B', 11); 
    map.Add('C', 12); 
    map.Add('D', 13); 
    map.Add('E', 14); 
    map.Add('F', 15); 
 
    // Convert given string to long 
    long m = long.Parse(k); 
 
    // Base to get 16 power 
    long Base = 1; 
 
    // Store N % K 
    long ans = 0; 
 
    // Iterate over the digits of N 
    for(int i = N.Length - 1; i >= 0; i--)
    { 
         
        // Stores i-th digit of N 
        long n = map[N[i]] % m; 
 
        // Update ans 
        ans = (ans + (Base % m * n % m) % m) % m; 
 
        // Update base 
        Base = (Base % m * 16 % m) % m; 
    } 
 
    // Print the answer converting 
    // into hexadecimal 
    Console.WriteLine(ans.ToString("X")); 
} 
 
// Driver Code 
public static void Main(String []args) 
{ 
     
    // Given string N and K 
    String n = "3E8"; 
    String k = "13"; 
 
    // Function Call 
    hexaModK(n, k); 
} 
} 
 
// This code is contributed by Princi Singh

Javascript

<script>
 
// Javascript program to implement
// the above approach
 
// Function to calculate modulus of
// two Hexadecimal numbers
function hexaModK(s, k)
{
     
    // Store all possible
    // hexadecimal digits
    var mp = new Map();
     
    // Iterate over the range ['0', '9']
    for(var i = 1; i <= 9; i++) 
    {
        mp.set(String.fromCharCode(
            i + '0'.charCodeAt(0)), i);
    }
     
    mp.set('A', 10);
    mp.set('B', 11);
    mp.set('C', 12);
    mp.set('D', 13);
    mp.set('E', 14);
    mp.set('F', 15);
     
    // Convert given string to long
    var m = parseInt(k, 16);
     
    // Base to get 16 power
    var base = 1;
     
    // Store N % K
    var ans = 0;
     
    // Iterate over the digits of N
    for(var i = s.length - 1;
            i >= 0; i--) 
    {
         
        // Stores i-th digit of N
        var n = mp.get(s[i]) % m;
         
        // Update ans
        ans = (ans + (base % m * n % m) % m) % m;
         
        // Update base
        base = (base % m * 16 % m) % m;
    }
    document.write(ans.toString(16).toUpperCase());
}
 
// Driver Code
 
// Given string N and K
var n = "3E8";
var k = "13";
 
// Function Call
hexaModK(n, k);
 
// This code is contributed by famously
 
</script>

Output:

Time Complexity: O(N)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!