A user can enter 0 or 1 which gets appended to a starting number which is 0.

Each time the user adds a digit, the program should tell if the whole number is divisible by 5 or not.

Example:

1. First number is 0.
2. User enters '1' - complete number is '1' - the answer is no.
3. User enters '0' - complete number is '10' - the answer is no.
4. User enters '1' - complete number is '101' - the answer is yes.

I know the answer has something to do with the last remainder and keeping the last remainder, but I can't find the exact calculation or the logic or the mathematics to do it.

``````int old_x = 0,new_x;
while(1)
{
scanf("%d",new_x);
new_x= ((old_x<<1)|new_x);
old_x = new_x ;
new_x = new_x%5;
if(!new_x)
{
printf("divisible by 5)
old_x = 0;
}
else
printf("not divisible by 5)
}
``````

In pseudocode:

``````remainder=0
while true {
remainder = remainder % 5
if remainder = 0
print "divisbile"
else
print "nondivisible"

remainder = (remainder<<1) + inputBit
}
``````

Explanation: if a number is divisible by 5 a multiple of that number is also divisible by 5, so that part is of no interest. Since your expansion can be modeled as a multiplication by two and an addition, this can be applied to your problem. Now all you do is to multiply the remainder and add the input and check if it is divisble.

The trick is that to know that if a number is divisible by 5 you only need to know the last decimal digit of the number. If it ends with 5 or 0 then it's divisible by 5. if it doesn't end with 5 or zero it needs an extra amount, which i call remainder to get there. Now given that you have the remainder you can reverse-engineer the last digit of the number. Then shift the last digit by 2 and add the new number the user types (d). Depening on d, you get the new last digit of the number. With that you can again see what newremainder must be added to get to the next multiple of 5.

``````int newRemainder[2][5] = {{0,2,4,1,3},{4,1,3,0,2}};
int remainder = 0;
int d;

while(1){
scanf("%d", &d);
remainder = newRemainder[d][remainder];
if (remainder ==0) printf("multiple");
}
``````

Top