Anuj has challenged Arun to climb N stairs but at only in powers of P and Q. Now Arun being a lazy guy wants to do this in minimum number of steps possible. So he has asked for your help to calculate the minimum number of steps he requires to take for climbing N stairs ( 1 step = some power of P or Q stairs (including zeroth power) ).
Example 1:
Input: 
N = 15, P = 2, Q = 3
Output:
3
Explanation:
We can make 15 by (8,4,3)
or (9,3,3) both takes 3 steps.
 
Example 2:
Input: 
N = 19, P = 4, Q = 3
Output:
2
Explanation:
In the second case, we can make
19 by (16,3) which is 2 steps.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function moves() which takes three integers N, P and Q as inputs and returns the number of steps that Arun needs to take to climb N stairs in powers of P & Q. If fit is not possible print -1.
 
Expected Time Complexity: O(N. log(N))
Expected Auxiliary Space: O(N. log(N))
 
Constraints:
1 ≤ N, P, Q ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Data structures

Starter code: #User function Template for python3



class Solution:    

    def moves(self,n, p, q):

       # Your code goes here 

        



Solutions:
from math import log

class Solution:

	def moves(self, n, p, q):
		if p == 1 and q == 1:
			return n
		if p == 1:
			p = q
		if q == 1:
			q = p
		setti = set([n])
		count = 0
		while 0 not in setti:
			new = set()
			for item in setti:
				new.add(item - p ** int(log(item, p)))
				new.add(item - q ** int(log(item, q)))
			setti = new
			count += 1
		return count


class Solution:

	def moves(self, n, p, q):

		def checker(n, p, dp):
			mul = 1
			if p == 1:
				return n
			ans = float('inf')
			while n - mul >= 0:
				ans = min(ans, dp[n - mul] + 1)
				mul = mul * p
			return ans
		dp = [float('inf')] * (n + 1)
		dp[0] = 0
		for i in range(1, n + 1):
			step1 = checker(i, p, dp)
			step2 = checker(i, q, dp)
			dp[i] = min(step1, step2)
		return dp[n]


class Solution:

	def moves(self, n, p, q):
		arr = [0] * (n + 1)
		arr[0] = 0

		def func(n, p, arr):
			a = 1
			ans = float('inf')
			if p == 1:
				return n
			while n - a >= 0:
				ans = min(ans, arr[n - a])
				a = a * p
			return ans + 1
		for i in range(1, n + 1):
			s1 = func(i, p, arr)
			s2 = func(i, q, arr)
			arr[i] = min(s1, s2)
		return arr[n]


import math
import sys
sys.setrecursionlimit(2000)

class Solution:

	def moves(self, n, p, q):
		if q == 1 and p == 1:
			return n
		elif q == 1:
			q = p
		elif p == 1:
			p = q
		dp = [float('inf') for i in range(n + 1)]
		dp[0] = 0
		for i in range(1, n + 1):
			powerQ = pow(q, int(math.log(i, q)))
			powerP = pow(p, int(math.log(i, p)))
			dp[i] = min(dp[i - powerQ], dp[i - powerP]) + 1
		return dp[n]


def moves(n, p, q):
	dp = [999999 for i in range(n + 1)]
	dp[0] = 0
	for i in range(1, n + 1):
		j = 0
		while i - pow(p, j) >= 0 and p != 1:
			dp[i] = min(dp[i], dp[i - pow(p, j)] + 1)
			j += 1
		j = 0
		while i - pow(q, j) >= 0 and q != 1:
			dp[i] = min(dp[i], dp[i - pow(q, j)] + 1)
			j += 1
		if p == 1 or q == 1:
			dp[i] = min(dp[i], dp[i - 1] + 1)
	return dp[n]

class Solution:
	x = 0


class Solution:
	pass

def moves(N, A, B):
	import math
	power_list = []
	na = 1
	nb = 1
	if A == 1:
		power_list.append(A)
	else:
		for i in range(1 + int(math.log(N, A))):
			power_list.append(A ** i)
	if B == 1:
		power_list.append(B)
	else:
		for i in range(1 + int(math.log(N, B))):
			power_list.append(B ** i)
	M = [float('inf') for _ in range(N + 1)]
	M[0] = 0
	for i in range(1, len(M)):
		if i in power_list:
			M[i] = 1
			continue
		if i < min(power_list):
			M[i] = -1
			continue
		mid = i // 2
		for x in power_list:
			if i > x:
				temp = 1 + M[i - x]
			M[i] = min(temp, M[i])
	return M[N]