Find minimal operations such that N will become 1 with 3 operations-CodePudding

We are given N as a natural number and we can do these 3 operations with him.

1)Subtract 1 from N

2)If it is even, divide by 2

3)If it divides 3, then divide by 3

We stop this when N becomes 1. We need to find minimal operations such that N will become 1

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'count' function below.
#
# The function is expected to return an INTEGER.
# The function accepts INTEGER num as parameter.
#

def count(num):
    
    count = 0 
    while num != 1:
        
        if (num % 3 ==0 ):
            count  = 1
            num = num / 3
        elif((num -1) % 3 == 0):
            count  = 2
            num = (num - 1) / 3
        elif (num % 2 ==0):
            count  = 1
            num = num / 2
        else:
            num = num - 1
            count  = 1 
            
    return count

This is my code. From 11 test cases it passed 9 and gave 2 wrong answers. I don't know for which test cases my code gives wrong answers. Can you help to understand where is problem?

CodePudding user response：

You make an assumption that it is better to subtract 1 and divide by 3 first if you can, but that isn't always true.

Consider 16

Your solution would be 16-15-5-4-3-1 = 5 steps

Better solution: 16-8-4-2-1 = 4 steps

CodePudding user response：

Probably not the most efficient solution but:

def count(num):
    count1, count2 = float('inf'), float('inf')

    if num == 1:
        return 0

    if num % 3 == 0:
        count1 = 1   count(num // 3)

    if num % 2 == 0:
        count2 = 1   count(num // 2)

    count3 = 1   count(num - 1)

    return min(count1, count2, count3)