Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to check for division by 7 for big number in C++?

I have to check, if given number is divisible by 7, which is usualy done just by doing something like n % 7 == 0, but the problem is, that given number can have up to 100000000, which doesn't fit even in long long.

Another constrain is, that I have only few kilobytes of memory available, so I can't use an array.

I'm expecting the number to be on stdin and output to be 1/0.

This is an example

34123461273648125348912534981264376128345812354821354127346821354982135418235489162345891724592183459321864592158
0

It should be possible to do using only about 7 integer variables and cin.get(). It should be also done using only standard libraries.

like image 494
Jakub Arnold Avatar asked Oct 11 '09 14:10

Jakub Arnold


People also ask

How do you know if a big number is divisible by 7?

The divisibility rule of 7 states that, if a number is divisible by 7, then “the difference between twice the unit digit of the given number and the remaining part of the given number should be a multiple of 7 or it should be equal to 0”. For example, 798 is divisible by 7.

How do you find divisibility by 7 in C?

Divisibility by 7 can be checked by a recursive method. A number of the form 10a + b is divisible by 7 if and only if a – 2b is divisible by 7. In other words, subtract twice the last digit from the number formed by the remaining digits.

How do you make a number divisible by 7?

Remove the last digit, double it, subtract it from the truncated original number and continue doing this until only one digit remains. If this is 0 or 7, then the original number is divisible by 7. Example: 1603 -> 160 – 2(3) = 154 -> 15 – 2(4) = 7, so 1603 is divisible by 7.

How do you find the divisibility of a big number?

For big numbers, alternately add and subtract digits in groups of three. If the answer is divisible by 7, the number is too. For example 256242 is divisible by 7 because 256-242 = 14. 8 If the last three digits form a number divisible by 8, then so is the whole number.


2 Answers

you can use a known rule about division by 7 that says: group each 3 digits together starting from the right and start subtracting and adding them alternativly, the divisibility of the result by 7 is the same as the original number:

ex.:

testing 341234612736481253489125349812643761283458123548213541273468213
        549821354182354891623458917245921834593218645921580

   (580-921+645-218+593-834+921-245+917-458+623-891+354-182
    +354-821+549-213+468-273+541-213+548-123+458-283+761-643
    +812-349+125-489+253-481+736-612+234-341 
    = 1882 )
    % 7 != 0 --> NOK!

there are other alternatives to this rule, all easy to implement.

like image 141
manji Avatar answered Oct 26 '22 13:10

manji


Think about how you do division on paper. You look at the first digit or two, and write down the nearest multiple of seven, carry down the remainder, and so on. You can do that on any abritrary length number because you don't have to load the whole number into memory.

like image 40
Paul Tomblin Avatar answered Oct 26 '22 14:10

Paul Tomblin