CODEWITHSUNDEEP
algorithmmathdivision
Rajat Bhadauria
Rajat Bhadauria

Reputation: 260

Minimum number of digits that need to be deleted, leaving a number divisible by 8

Given a number as n

We have to find minimum number of deletion of its digit to find whether number is divisible by 8 ?

e.g.
2156

minimum number of deletion required here is 1 as deleting 1 from it results number 256 which is divisible by 8

256 ...Here  answer is 0 
12156    Here answer is 1
256111 here answer is 3

Upvotes: 1

Views: 945

Answers (2)

Bill Lynch
Bill Lynch

Reputation: 81926

So there's a general solution for these kinds of problems. You basically want to perform a breadth-first search of the solution space. The easiest way to do that, is with a queue:

  1. Create a queue.
  2. Insert your start item into the queue (2156 for example)
  3. Pop the bottom of the queue (2156)
  4. Test 2156 to see if it meets your requirements.
  5. If it does, then we're done.
  6. Otherwise, compute all of it's children: 156, 256, 126, 215
  7. Push all of those children into the queue.
  8. If the queue is not empty, goto step 3.
  9. If we reach this point, there is no number that is divisible by 8.

So, in code, we might do something like this:

from queue import Queue
import itertools

def main():
    queue = Queue()
    queue.put_nowait("256111")

    while queue:
        item = queue.get_nowait()

        if item == '':
            item = '0'

        if int(item) % 8 == 0:
            print(item)
            return

        for child in itertools.combinations(item, len(item) - 1):
            queue.put_nowait(''.join(child))

if __name__ == '__main__':
    main()

Upvotes: 0

ig-melnyk
ig-melnyk

Reputation: 2879

Well,first you need to know that number divides by 8 only if last 3 digits divide by 8. Number xyz(x*10^2+y*10+z) divides by 8 only if 4*x+2*y+z divides by 8. So I suggest to calculate all possible pairs of length 2 for each possible module by 8.

For example, our number equals : 321321342. z equals 2. So we need to find such pair (x,y) that (4*x+2*y)%8 = 6 because (4x+2y+z)%8 must equal zero. So we build a dictionary whose keys will be (4x+2y) and values will be pair of indexes (i,j) for values x and y. After that, you will need to iterate over all possible z-values and take a minimum result. Algorithm will be O(n^2) complexity

And here's some code :

def solve(a):
        lst = digits(a)
        results = []
        d=collections.defaultdict(list)
        for i in range(1,len(lst)-1):
                    for j in range(i+1,len(lst)):
                            d[(4*lst[j]+2*lst[i])%8].append((i,j))
        for i in range(len(lst)-2):
            z = lst[i]
            if z%2==1:
                continue
            pairs = d[8-z]
            for k,v in pairs:
                if i>=k:
                    pass
                else:
                    results.append((i,k,v))
        return results

Function "solve" returns list of possible indexes of array values that together divide by 8. 

def solveNumberResult(number):
  result = solve(number)
  mn = result[0]
  for i,j,k in result:
    if sum(mn)>i+j+k:
        mn=(i,j,k)
  return i+(j-i-1)+(k-j-1)

Takes the result of the solve function and after that finds the optimal number of digit's deletions. 

solveNumberResult(256111) =>3 
solveNumberResult(256)    =>0
solveNumberResult(2156)   =>1

Hope,it works

Upvotes: 2

Related Questions