I was solving this dynamic programming problem, and I was wondering if I can get any code review and feedback. You can find this problem online.
# Coding Problem: Minimum Steps to One # # Prompt: Given a positive integer, you can perform any combination of these 3 steps: # 1.) Subtract 1 from it. # 2.) If its divisible by 2, divide by 2. # 3.) If its divisible by 3, divide by 3. # # Find the minimum number of steps that it takes get from N to1 #
def min_steps_to_one(n): work = [0, 0] for i in range(2, n+1): min_choice = work[i-1] if i % 3 == 0: divide_by_three = work[i//3] min_choice = min(min_choice, divide_by_three) if i % 2 == 0: divide_by_two = work[i//2] min_choice = min(min_choice, divide_by_two) work.append(min_choice + 1) return work[n]
I also include some test cases for Minimum Steps to One Tests
- true: should return 3 for 10
- true: should return 0 for 1
- true: should work for large numbers PASSED: 3 / 3
def expect(count, name, test): if (count is None or not isinstance(count, list) or len(count) != 2): count = [0, 0] else: count += 1 result = 'false' error_msg = None try: if test(): result = ' true' count += 1 except Exception as err: error_msg = str(err) print(' ' + (str(count) + ') ') + result + ' : ' + name) if error_msg is not None: print(' ' + error_msg + '\n') print('Minimum Steps to One Tests') test_count = [0, 0] def test(): example = min_steps_to_one(10) return example == 3 expect(test_count, 'should return 3 for 10', test) def test(): example = min_steps_to_one(1) return example == 0 expect(test_count, 'should return 0 for 1', test) def test(): example = min_steps_to_one(1334425) return example == 22 expect(test_count, 'should work for large numbers', test) print('PASSED: ' + str(test_count) + ' / ' + str(test_count) + '\n\n')