Exchanging coin dp

#1

in this question n should be divisible by all three??

#2

@shampblocks no its not possible everytime lets take a example n=27
n/2 gives 13
n/3 gives 9
n/4 gives 6
so ans 28 and in this it don’t divide 2 and 4
so conclusion it dont matter whether divides or not.
dont forget to hit like and mark resolved if cleared :smiley:

#3

so i dont have to check for divisibility just check for lower subtree for divided value?? like for n==27 if n/2 we do we get 13 so i should check for 13 or not??

#4

yes dont check whether its divided or not just do it

#5


hello sir i have done this question it is passed but i m confused in how to calculate its time complexity??

#6

IMG-20200614-WA0003
IMG-20200614-WA00031280×720 54.4 KB

here look so many overlapping subproblems so time complexity would be aprrox o(n)
only left side ans will be calculated in right side we directly use dp

#7

i solved recurrence by brute force my complexity coming 3^(logn +1) we can take 3 as 2 to make time complexity O(n)??

#8

@shampblocks yes sorry it would be o(n) if operations given n-2,n-3,n-4 , your complexity is right my mistake

#9

but remove 3^ @shampblocks
it should be o(logn)

#10

so it should be o(n) for recursive breute force but when i am memoizing it how to calculate time complexity??

#11

@shampblocks
for recursive bruteforce your correct
for memorising see the photo you only have to go bottom of tree once in left all other values(most of them will be calculated) so complexity o(logn)

#12

for brute force it would be n i think

#13

how? @shampblocks see the graph at every step dividing into 3

#14

i am thinking in this way log(n) base 2 + log(n) base 4 +log(n) base 3 so time complexity would be 3*log(n) base …is it correct way??

#15

brute force means when i am not memoizing it

#16

@shampblocks well if you think properties of log then 3^(log3n) is n only so yes its nearly equal n
if we consider log3n+log2n+log4n as log3n

#17

tell me about this??

#18

what should i tell you about?

#19

i am thinking in this way log(n) base 2 + log(n) base 4 +log(n) base 3 so time complexity would be 3*log(n) base …is it correct way??

#20

for memorising you are telling it?