Check if a larger number divisible by 36 - GeeksforGeeks

Check if a larger number divisible by 36 - GeeksforGeeks
Given a number, check whether a given number is divisible by 36 or not. The number may be very large and may not fit in any numeric(int, long int, float, etc.) data type.

 number is divisible by 36 if the number is divisible by 4 and 9

1. A number is divisible by 4 if the number formed by its last 2 digits is divisible by 4
2. A number is divisible by 9 if the sum of the digits of the number is divisible by 9

string divisibleBy36(string num)

{

    int l = num.length();

    // null number cannot

    // be divisible by 36

    if (l == 0)

        return "No";

    // single digit number other than

    // 0 is not divisible by 36

    if (l == 1 && num[0] != '0')

        return "No";

    // number formed by the last 2 digits

    int two_digit_num = (num[l-2] - '0')*10 +

                        (num[l-1] - '0') ;

    // if number is not divisible by 4

    if (two_digit_num%4 != 0)

        return "No";

    // number is divisible by 4 calculate

    // sum of digits

    int sum = 0;

    for (int i=0; i<l; i++)

        sum += (num[i] - '0');

    // sum of digits is not divisible by 9

    if (sum%9 != 0)

        return "No";

    // number is divisible by 4 and 9

    // hence, number is divisible by 36

    return "Yes";

}

http://www.geeksforgeeks.org/check-large-number-divisible-9-not/

Given a number, the task is to find if the number is divisible by 9 or not. The input number may be large and it may not be possible to store even if we use long long int.

A number is divisible by 9 if sum of its digits is divisible by 9.

http://www.geeksforgeeks.org/check-large-number-divisible-4-not/

A number is divisible by 4 if number formed by last two digits of it is divisible by 4.

http://www.geeksforgeeks.org/check-large-number-divisible-6-not/

Given a number, the task is to check if a number is divisible by 6 or not. The input number may be large and it may not be possible to store even if we use long long int.

A number is divisible by 6 it's divisible by 2 and 3. 
a)  A number is divisible by 2 if its last digit is divisible by 2.
b)  A number is divisible by 3 if sum of digits is divisible by 3.

bool check(string str)

{

    int n = str.length();

    // Return false if number is not divisible by 2.

    if ((str[n-1]-'0')%2 != 0)

       return false;

    // If we reach here, number is divisible by 2.

    // Now check for 3.

    // Compute sum of digits

    int digitSum = 0;

    for (int i=0; i<n; i++)

        digitSum += (str[i]-'0');

    // Check if sum of digits is divisible by 3

    return (digitSum % 3 == 0);

}

http://www.geeksforgeeks.org/check-large-number-divisible-8-not/

Given a number, the task is to check if a number is divisible by 8 or not. The input number may be large and it may not be possible to store even if we use long long int.

A number is divisible by 8 if number formed by last three digits of it is divisible by 8.

bool check(string str)

{

    int n = str.length();

    // Empty string

    if (n == 0)

        return false;

    // If there is single digit

    if (n == 1)

        return ((str[0]-'0')%8 == 0);

    // If there is double digit

    if (n == 2)

        return (((str[n-2]-'0')*10 + (str[n-1]-'0'))%8 == 0);

    // If number formed by last three digits is

    // divisible by 8.

    int last = str[n-1] - '0';

    int second_last = str[n-2] - '0';

    int third_last = str[n-3] - '0';

    return ((third_last*100 + second_last*10 + last) % 8 == 0);

}

http://www.geeksforgeeks.org/check-large-number-divisible-11-not/

Given a number, the task is to check if the number is divisible by 11 or not. The input number may be large and it may not be possible to store it even if we use long long int.

A number is divisible by 11 if difference of following two is divisible by 11.

1. Sum of digits at odd places.
2. Sum of digits at even places.

Let us consider 7694, we can write it as
7694 = 7*1000 + 6*100 + 9*10 + 4

The proof is based on below observation:
Remainder of 10i divided by 11 is 1 if i is even
Remainder of 10i divided by 11 is -1 if i is odd

So the powers of 10 only result in values either 1 
or -1. 

Remainder of "7*1000 + 6*100 + 9*10 + 4"
divided by 11 can be written as : 
7*(-1) + 6*1 + 9*(-1) + 4*1

The above expression is basically difference 
between sum of even digits and odd digits.

int check(string str)

{

    int n = str.length();

    // Compute sum of even and odd digit

    // sums

    int oddDigSum = 0, evenDigSum = 0;

    for (int i=0; i<n; i++)

    {

        // When i is even, position of digit is odd

        if (i%2 == 0)

            oddDigSum += (str[i]-'0');

        else

            evenDigSum += (str[i]-'0');

    }

    // Check its difference is divisble by 11 or not

    return ((oddDigSum - evenDigSum) % 11 == 0);

}

http://www.geeksforgeeks.org/write-an-efficient-method-to-check-if-a-number-is-multiple-of-3/
Write an Efficient Method to Check if a Number is Multiple of 3

The very first solution that comes to our mind is the one that we learned in school. If sum of digits in a number is multiple of 3 then number is multiple of 3 e.g., for 612 sum of digits is 9 so it’s a multiple of 3. But this solution is not efficient. You have to get all decimal digits one by one, add them and then check if sum is multiple of 3.

There is a pattern in binary representation of the number that can be used to find if number is a multiple of 3. If difference between count of odd set bits (Bits set at odd positions) and even set bits is multiple of 3 then is the number.

Example: 23 (00..10111)
1) Get count of all set bits at odd positions (For 23 it’s 3).
2) Get count of all set bits at even positions (For 23 it’s 1).
3) If difference of above two counts is a multiple of 3 then number is also a multiple of 3.

(For 23 it’s 2 so 23 is not a multiple of 3)

Above can be proved by taking the example of 11 in decimal numbers. (In this context 11 in decimal numbers is same as 3 in binary numbers)
If difference between sum of odd digits and even digits is multiple of 11 then decimal number is multiple of 11. Let’s see how.

Let’s take the example of 2 digit numbers in decimal
AB = 11A -A + B = 11A + (B – A)
So if (B – A) is a multiple of 11 then is AB.

Let us take 3 digit numbers.

ABC = 99A + A + 11B – B + C = (99A + 11B) + (A + C – B)
So if (A + C – B) is a multiple of 11 then is (A+C-B)

Let us take 4 digit numbers now.
ABCD = 1001A + D + 11C – C + 999B + B – A
= (1001A – 999B + 11C) + (D + B – A -C )
So, if (B + D – A – C) is a multiple of 11 then is ABCD.

int isMultipleOf3(int n)

{

    int odd_count = 0;

    int even_count = 0;

 

    /* Make no positive if +n is multiple of 3

       then is -n. We are doing this to avoid

       stack overflow in recursion*/

    if(n < 0)   n = -n;

    if(n == 0) return 1;

    if(n == 1) return 0;

 

    while(n)

    {

        /* If odd bit is set then

           increment odd counter */

        if(n & 1)

           odd_count++;

        n = n>>1;

 

        /* If even bit is set then

           increment even counter */

        if(n & 1)

            even_count++;

        n = n>>1;

    }

 

     return isMultipleOf3(abs(odd_count - even_count));

}

Read full article from Check if a larger number divisible by 36 - GeeksforGeeks