- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Suppose we have a number n. So consider there are n oranges in the kitchen and we eat some of these oranges every day maintaining these rules: 1. Eat single orange. 2. If n is even, then eat n/2 oranges. 3. If n is divisible by 3 can eat 2*(n/3) oranges. We can select only one option each day. We have to find the minimum number of days to eat n oranges.

So, if the input is like n = 10, then the output will be 4 because

On day 1 eat 1 orange, 10 - 1 = 9.

On day 2 eat 6 oranges, 9 - 2*(9/3) = 9 - 6 = 3.

On day 3 eat 2 oranges, 3 - 2*(3/3) = 3 - 2 = 1.

On day 4 eat the last orange 1 - 1 = 0.

To solve this, we will follow these steps −

Define a function fun() . This will take n

if n is in memo, then

return memo[n]

if n<=2, then

return n

memo[n]:= 1 + minimum of (n mod 2+ fun(quotient of n/2)) and (n mod 3 + fun(quotient of n/3))

return memo[n]

From the main method, do the following

memo:= a new map

return fun(n)

Let us see the following implementation to get better understanding

def solve(n): def fun(n): if n in memo: return memo[n] if n<=2: return n memo[n]=1+min(n%2+fun(n//2),n%3+fun(n//3)) return memo[n] memo={} return fun(n) n = 12 print(solve(n))

7, [5,1,4,3]

4

- Related Questions & Answers
- Program to find minimum number of days to wait to make profit in python
- Program to find minimum number of days to make m bouquets using Python
- Program to find minimum number of Fibonacci numbers to add up to n in Python?
- Python program to find number of days between two given dates
- Program to find minimum number of people to teach in Python
- Program to find minimum bus fare for travelling all days in Python?
- Program to find minimum number of groups in communication towers in C++?\n
- Program to find minimum number of monotonous string groups in Python
- Program to find minimum space plane required for skydivers in k days in python
- Program to find number of days it will take to burn all trees in python
- Program to find number of minimum steps to reach last index in Python
- Program to find minimum number of operations to make string sorted in Python
- Program to find minimum number of rocketships needed for rescue in Python
- Program to find minimum number of operations required to make one number to another in Python
- Program to find higher number with same number of set bits as n in Python?\n

Advertisements