CareerCup

public boolean isMultiplesOfFive(int a) {
	int mask = 5;
	while ((mask << 1) < a) {
		mask <<= 1;
	}

	while (mask >= 5) {
		if (a >= mask) {
			a -= mask;
		}
		mask >>= 1;
	}
	return a == 0;
}

Here is simple code in java. Steps are as following
1. Divisibility can be checked by checking whether last digit is 0 or 5.
2. Since complexity should be o(logn) .
3. If number is odd we can add 5 in it.
5. After that we have to check whether last digit is 0 or not.
6. Now u we can multiply it with 0.1 and after that we can cast it again in int.
7.Then multiply with ten.
8.After all these processes we should get the old number back;
9.If we dont get it number is not divisible.

static boolean check(int x) {
        if((x&1)==1)
            x+=5;
        float y=((int)(x*0.1))*10;
        if(y==x)
            return true;
        else return false;
    }

Another weird solution could be:

Convert the number into string and check if the last character in the string is either a 5 or 0.
If yes, then the number is multiple of 5. else not.

A multiple of 5 means the number can be divided by 10 directly or by 10 after +5, so it turns out to be the question: how to determine the given number can be divided by 10, without / or %, you can use bit operation to determine.

how is this one?

bool isMultiplyOf5(int n)
{
bool is5 = false;
int i = 0;
int cur = 5;
for (; i < n; i ++) {
if (cur*5 > n) {
n -= cur;

if (n == 5 || n == 0) {
is5 = true;
break;
}
else if (n < 5 && n > 0) {
break;
}
else if(n > 5)
{
cur = 5;
continue;
}
}
else if(cur == n)
{
is5 = true;
break;
}
else
{
cur *= 5;

}
}

return is5;
}

One way to solve in Python could be

def isMultipleOfFive(x):
if int(list(str(x))[-1]) in [0,5]:
return True
else:
return False

int division(int tempdividend, int tempdivisor) {

int quotient = 1;

if (tempdivisor == tempdividend) {
remainder = 0;
return 1;
} else if (tempdividend < tempdivisor) {
remainder = tempdividend;
return 0;
}

do{

tempdivisor = tempdivisor << 1;
quotient = quotient << 1;

} while (tempdivisor <= tempdividend);



/* Call division recursively */
quotient = quotient + division(tempdividend - tempdivisor, divisor);

return quotient;
}


void main() {

printf ("\nEnter the Dividend: ");
scanf("%d", &dividend);
printf("\nEnter the Divisor: ");
scanf("%d", &divisor);

printf("\n%d / %d: quotient = %d", dividend, divisor, division(dividend, divisor));
printf("\n%d / %d: remainder = %d", dividend, divisor, remainder);
getch();
}

#include <stdio.h>
#include <string.h>

int main (int argc, char *argv[])
{
   int size=0;

   size = strlen(argv[1]);

   if ( argv[1][size-1]  == '0' ||  argv[1][size -1] == '5' )
       printf("\nNumber divisible 5");
   else
       printf("\nNumber Not divisible 5");


   return 0;
}

bool isDivisibleBy5(int a)
{
 if(a&1)
 {
  if((a+5) & 1)
   return false;
  else
   return true;
 }
 else
 {
   if((a+5) & 1)
   return true;
  else
   return false;
 }
}

#include<stdio.h>
#include<conio.h>
void main()
{
char *s;
int k,i=0;
printf("enter number");
gets(s);
while(*(s+i)!='\0')
{
i=i+1;
}
i=i-1;
if(*(s+i)== '5' || *(s+i) =='0')
{
printf("divisible by 5");
}
else
{
printf("undivisible by 5");
}

getch();
}

Having a string as input, the problem becomes only checking wether the last char of the string is equals to 0 or 5.

In python, it would be:

last = sys.argv[1][len(sys.argv[1])-1]
print 'last digit: ' + last
if last == '5' or last == '0':
    print 'Yes!'
else:
    print 'No!'

If I am calculating it correctly, this is O(1), but I find it suspiciously easy.

Am I doing it right?

How about doing a binary search? Let's assume the input is n. If n is a multiple of 5, then it can be written that n = 5*x. We set low = 1, high = n, and try to find x using a binary search. Note that since w can't use / operator, we need to use right shift for computing mid = (low + high) >> 1.

bool divisabelBy5 (unsigned int n)
{
if (n < 5)
return false;

n -= 5;

if (n & 0x1)
return false;

n >>= 1;

int d = 0;

while (n) {
if (n & 0x1) d += 2;
if (n & 0x2) d += 4;
if (n & 0x4) d += 8;
if (n & 0x8) d += 6;

if (d >= 20) d -= 20;
else if (d >= 10) d -= 10;

n >>= 4;
}

return d == 0;
}

public static boolean mask(int a){
int maskValue = 5;
boolean result = false;
if(a<maskValue && a != 0)
return result;
while(a>=maskValue){
a -= maskValue;
}
if (a == 0)
result = true;
else
result = false;
return result;
}

public boolean test(int n)
{
int temp=n*0.1;
temp=temp*10;
if(n-temp==0 || n-temp==5)
{
return true;
}
else
{
return false;
}
}

}

bool check(int a){
    int mask = 5;
    if(a < 0) a*=-1;  // if a is -ve
    if(a < mask) return 0;  // False
    while((mask << 2) < a){
        count++;
        mask=mask << 2;
    }
    if (mask==a) return 1;  // True
    return check(a-mask);
}

Algo:-
1. if number is greater than 5, check if odd. If odd, subtract 5.
2. if even, divide by 2. until it becomes an odd.
3. check in n=5.

The number will finally reduce to 5.

code:

public static boolean divisibleByFive(int n){
	if(n==0)
		return true;
	if(n<0)
		return divisibleByFive(n*(-1));
	while(n>=5){
		//if even divide by 2, until it becomes odd
		while((n&1)==0)
			n=n>>1;
		//now check if equal to 5.
		if(n==5)
			return true;
		else 
			n=n-5;
	}
	return false;
}

I feel i am missing something crucial here. if the number ends with a 0 or a 5, it is definitely divisible by 5. this is not a good question

Just found another way from geeks for geeks website.
A number n can be a mulpile of 5 in two cases. When last digit of n is 5 or 10. If last bit in binary equivalent of n is set (which can be the case when last digit is 5) then we multiply by 2 using n<<=1 to make sure that if the number is multpile of 5 then we have the last digit as 0. Once we do that, our work is to just check if the last digit is 0 or not, which we can do using float and integer comparison trick.

#include<stdio.h>
 
bool isMultipleof5(int n)
{
    /* If n is a multiple of 5 then we make sure that last 
       digit of n is 0 */
    if ( (n&1) == 1 )
        n <<= 1;
     
    float x = n;
    x = ( (int)(x*0.1) )*10;
     
    /* If last digit of n is 0 then n will be equal to (int)x */
    if ( (int)x == n )
        return true;
 
    return false;
}
 
/* Driver program to test above function */
int main()
{
    int i = 19;
    if ( isMultipleof5(i) == true )
        printf("%d is multiple of 5\n", i);
    else
        printf("%d is not a multiple of 5\n", i);
 
    getchar();
    return 0;
}

Just found another way from geeks for geeks website.
A number n can be a mulpile of 5 in two cases. When last digit of n is 5 or 10. If last bit in binary equivalent of n is set (which can be the case when last digit is 5) then we multiply by 2 using n<<=1 to make sure that if the number is multiple of 5 then we have the last digit as 0. Once we do that, our work is to just check if the last digit is 0 or not, which we can do using float and integer comparison trick.

#include<stdio.h>
 
bool isMultipleof5(int n)
{
    /* If n is a multiple of 5 then we make sure that last 
       digit of n is 0 */
    if ( (n&1) == 1 )
        n <<= 1;
     
    float x = n;
    x = ( (int)(x*0.1) )*10;
     
    /* If last digit of n is 0 then n will be equal to (int)x */
    if ( (int)x == n )
        return true;
 
    return false;
}
 
/* Driver program to test above function */
int main()
{
    int i = 19;
    if ( isMultipleof5(i) == true )
        printf("%d is multiple of 5\n", i);
    else
        printf("%d is not a multiple of 5\n", i);
 
    getchar();
    return 0;
}

think about how division is implemented on computer?
5 is 101;
20 is 10100;
if you left shift 101 for 2 bit, you will get 20, so ....

bool check(int a)
{
float b = ((float)(a << 1 )) * 0.1;
int c = b;
return c * 5 = = a;
}