CODEWITHSUNDEEP
python
Mo Samani
Mo Samani

Reputation: 53

changing base of a number to a given number

I must write a recursive function that gets a number(n) in the 10 base and converts it to a given number base(k) and return a list which its components are the final number digits,for example f(5, 3) must result [1, 2] which 5 in base 3 is 12, or f(22, 3) must result [2, 1, 1].

Here's the code I tried:

def cb(n, k):
    b = []
    if n == 0:
        b.append(0)
    if n < k:
        b.append(n)
    if n == k:
        b.append(10)
    else:
        a = n // k
        b.append(n - ((n // k) * k))
        if a < k:
            b.append(a)
        else:
            cb(a, k)

    return b

print(cb(22, 3))

Actually I thought a lot on it but since I'm not so good at writing codes I couldn't go any further. I appreciate your help and modifications to my code .

Upvotes: 1

Views: 299

Answers (3)

m7mdbadawy
m7mdbadawy

Reputation: 920

If you think in terms of recursion the base case is when n < k for which the answer is n and to get the last digit of the n you do n%k so the recusive case is cb(n//k,k)+[n%k].

The code will look like this :

def cb(n, k):
    if n < k:
        return [n]
    else:
        return cb(n//k, k) + [n%k]

print(cb(22, 3))

Upvotes: 8

Jeremy West
Jeremy West

Reputation: 12685

The biggest problem is that you aren't doing anything with the results of the recursive call, so they never go in your list. I think you are also complicating this too much. Something like this should work:

def cb(n,k):
  if n > 0:
    q = n // k
    r = n - q * k
    b = cb(q, k)
    b.append(r)
  else:
    b = [0]

  if b[0] == 0 and len(b) > 1:
    b = b[1:]

  return b

I think if you don't do the last part, then you always get a 0 on the front? You could also simplify it further by just testing to see if it is less than the radix, which gives an even simpler solution

def cb(n,k):
  if n < k:
    return [n]
  else:
    q = n // k
    r = n - q * k
    b = cb(q, k)
    b.append(r)
    return b

Upvotes: 1

R Nar
R Nar

Reputation: 5515

you were very close, the only thing that you needed to do was change:

    else:
        cb(a, k)

to:

    else:
        b.extend(cb(a, k))

however, your output is going to be:

>>> cb(22, 3)
[1, 1, 2]

which is the reverse of what you want, since 22 in base 3 is 211. you can fix this by either reversing the list [1,1,2][::-1] == [2,1,1] or replace all your calls to append and your new call to extend to instead add at the beginning of the list like: b.insert(0,element) or b = cb(a,k) + b

Upvotes: 2

Related Questions