All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
Divisible by B (Posted on 2023-02-10) Difficulty: 3 of 5
Devise an algorithm to determine whether a given positive hexadecimal integer N is divisible by (B)16, and if NOT, to find the remainder.

N can contain up to (20220)10 digits.

Note:
o Simply dividing N by (B)16 is NOT permissible.
o (B)16 is equal to 11 in base ten.

See The Solution Submitted by K Sengupta    
Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Algorithm and Program Comment 2 of 2 |
Input a hex number as a string, convert to a list and any letters to uppercase.
Will plan to go from left to right, ie loop through the list of hex digits.
Initialize carry = 0
Since we are dividing by 11, carry can be any integer from 0 to 10.
We are interested in 16 times the carry plus the current digit, but we can make that nicer and equivalent mod 11 by being interested in 5 times the carry plus the current digit.  But we can make it even nicer by making a list with 11 entries of what will be the mod 11 contribution of the carry to the next carry.   That list is:
prior = [0,5,10,4,9,3,8,2,7,1,6]
And prior[carry] is the contribution to the next carry.
Also, let's make a dictionary where "key" is any hex digit and "value" is the decimal equivalent.

The next carry is the mod 11 value of (currentDigit plus prior[carry])
When there are no more digits, final carry value is the answer.


[If we were not even allowed to do the mod11 step, we could make a larger dictionary where the keys would be the concatenations of every possible carry with every possible current digit (11*16=176 entries) and the values the corresponding carry. I did not write the code for this part however] 

the following I believe will work on a hexadecimal integer of however many digits the programming language and machine constraints allow.
-----------------------
prior = [0,5,10,4,9,3,8,2,7,1,6]
hexDigits = {}
for i in range(16):
    hexDigits[str(base2base(i,10,16))] = i

def r(str16):
    """ string16 is a string version of a base 16 number
    output the remainder if you divide by hex B  or dec 11  """
    carry = 0
    list16 = list(str16.upper())
    for d in list16:
        carry = (prior[carry] + hexDigits[d])%11
    if carry == 0:
        print(str16.upper(), 'is divisible by hex B.')
    return carry


  Posted by Larry on 2023-02-10 12:58:16
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (12)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information