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

Home > Algorithms
Divisible by 11 (Posted on 2008-01-02) Difficulty: 3 of 5
Give an algorithm that determines whether a given number is divisible by 11 or not. The number could have up to one million digits.

(Note that simply dividing by 11, or doing long division by 11 is not allowed as a solution.)

See The Solution Submitted by Chesca Ciprian    
Rating: 1.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution as a computer program | Comment 2 of 3 |

So as not to overflow, the individual odd and even digit counters are kept mod 11. The digits are read off a file. Anything other than a digit or a comma stops the number, and commas are ignored.  As a bonus, the congruence mod 11 is given.

OPEN "number.txt" FOR BINARY AS #1
dig$ = " "
DO
  GET #1, , dig$
  IF EOF(1) THEN EXIT DO
  IF INSTR("0123456789,", dig$) = 0 THEN EXIT DO
  IF INSTR("0123456789", dig$) > 0 THEN
    digNo = (digNo + 1) MOD 2
    ct(digNo) = ct(digNo) + VAL(dig$)
    IF ct(digNo) > 10 then ct(digNo) = ct(digNo) - 11
  END IF
  PRINT dig$;
LOOP
CLOSE
PRINT
IF digNo THEN
 diff = ct(1) - ct(0)
ELSE
 diff = ct(0) - ct(1)
END IF

IF diff < 0 THEN diff = diff + 11

PRINT "mod 11 = "; diff
PRINT "Therefore it is ";
IF diff > 0 THEN PRINT "not ";
PRINT "divisible by 11."


122
mod 11 =  1
Therefore it is not divisible by 11.
121
mod 11 =  0
Therefore it is divisible by 11.
1111
mod 11 =  0
Therefore it is divisible by 11.
1,111
mod 11 =  0
Therefore it is divisible by 11.
1,113
mod 11 =  2
Therefore it is not divisible by 11.
1,113,678,992,376
mod 11 =  5
Therefore it is not divisible by 11.
1,113,678,992,376,777,565,492,365,555,123
mod 11 =  4
Therefore it is not divisible by 11.
1,113,678,992,376,777,565,492,365,555,119
mod 11 =  0
Therefore it is divisible by 11.
11
mod 11 =  0
Therefore it is divisible by 11.
12
mod 11 =  1
Therefore it is not divisible by 11.
19
mod 11 =  8
Therefore it is not divisible by 11.
1
mod 11 =  1
Therefore it is not divisible by 11.
1589123477421159822231568945667123566842255778988874445612358974100230145054123
mod 11 =  3
Therefore it is not divisible by 11.

Verification of this last by extended precision UBASIC:
a=158912347742115982223156894566712356684225577898887444561235897410023014505412
3
OK
?a@11
 3
OK

 


  Posted by Charlie on 2008-01-02 18:04:12
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 (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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