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.
http://www.geeksforgeeks.org/check-large-number-divisible-9-not/
http://www.geeksforgeeks.org/check-large-number-divisible-4-not/
http://www.geeksforgeeks.org/check-large-number-divisible-8-not/
http://www.geeksforgeeks.org/check-large-number-divisible-11-not/
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
Read full article from 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
- A number is divisible by 4 if the number formed by its last 2 digits is divisible by 4
- 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-6-not/A number is divisible by 4 if number formed by last two digits of it is divisible by 4.
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.
- Sum of digits at odd places.
- 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.
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.
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.
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)
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.
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));
}