|
Given a large number n, find if the number is divisible by 29.
Examples :
Input : 363927598
Output : No
Input : 292929002929
Output : Yes
A quick solution to check if a number is divisible by 29 or not is to add 3 times of last digit to rest number and repeat this process until number comes 2 digit. The given number is divisible by 29 if the obtained two digit number is divisible by 29.
Number is 348,
Three times of last digit + Rest of the number = 8*3 + 34 = 58
Since 58 is divisible by 29, 348 is also divisible by 29.
C++
<?php
function isDivisible($n)
{
while (intval($n / 100))
{
$last_digit = $n % 10;
$n = intval($n / 10);
$n += $last_digit * 3;
}
return ($n % 29 == 0);
}
$n = 348;
if (isDivisible($n))
echo "Yes";
else
echo "No" ;
?>
|
Javascript
<script>
function isDivisible(n)
{
while (parseInt(n / 100))
{
let last_digit = n % 10;
n = parseInt(n / 10);
n += last_digit * 3;
}
return (n % 29 == 0);
}
let n = 348;
if (isDivisible(n))
document.write("Yes");
else
document.write("No") ;
</script>
|
Time Complexity: O(n) where n is given number.
Space Complexity: O(1) as we are not using any extra space.
|
