I wonder if there is a way to count the number of zero digit in an integer number by using only these operations: , -, * and / Others operations such as cast, div, mod, ... are not allowed.

Input: 16085021 Output: 2

CodePudding user response：

It is a major restriction that numbers cannot be compared in a way to know that one is less than the other, and only equality checks can be done.

In my opinion that means there is nothing much else you can do than repeatedly add 1 to a variable until it hits a target (n) and derive from that what the least significant digit is of the original number n. This is of course terribly slow and not scalable, but it works in theory.

Here is a demo in Python using only ==, , - and /:

n = 16085021

count = 0
while True:
    # find out what least significant digit is
    digit = 0
    i = 0
    while True:
        if n == i:
            break
        digit = digit   1
        if digit == 10:
            digit = 0
        i = i   1
    # count any zero digit
    if digit == 0:
        count = count   1
    # shift that digit out of n
    n = (n - digit) / 10
    if n == 0:
        break

print(count)  # 2

CodePudding user response：

Modulo can be implemented with subtractions: a % b = subtract b from a until you end up with something < b and that's the result. You say we can only use the == comparison operator, but we are only interested in modulo 10, so we can just check equality to 0, 1, ..., 9.

def modulo10WithSubtractions(a):
    if a == 0 || a == 1 || ... || a == 9:
        return a
    while True:
        a = a - b
        if a == 0 || a == 1 || ... || a == 9:
            return a

Integer division by 10 can be implemented in a similar fashion: a // 10 = add 10 to itself as many times as possible without exceeding a.

def div10WithAdditions(a):
    if a == 0 || a == 1 || ... || a == 9:
        return 0

    k = 0
    while True:
        k  = 1
        if a - k*10 == 0 || a - k*10 == 1 || ... || a - k*10 == 9:
            return k

Then we can basically do the classical algorithm:

count = 0
while True:
    lastDigit = modulo10WithSubtractions(a)
    if lastDigit == 0:
        count  = 1
    a = div10WithAdditions(a)
    if a == 0:
        break

CodePudding user response：

Asuuming / means integer division, then this snippet does the job.

int zeros = 0;
while(num > 0){
  if(num / 10 == (num   9) / 10){
    zeros  ;
  }
  num /= 10;
}