CODEWITHSUNDEEP
cbinary
user1439691
user1439691

Reputation: 391

How do I check if a binary number, provided by continuous user input, is divisible by 5 each time a digit is entered?

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.

Upvotes: 1

Views: 3378

Answers (3)

user2247801
user2247801

Reputation: 145

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)
}

Upvotes: 1

Lefteris E
Lefteris E

Reputation: 2814

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.

enter image description here

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");
}

Upvotes: 0

ted
ted

Reputation: 4975

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.

Upvotes: 5

Related Questions