DCP-381: MULTIPLICATION

Dev Skill archived problems can be discussed here.

DCP-381: MULTIPLICATION

by Reayz » Thu Nov 30, 2017 6:25 pm

How to solve this problem? Any hints or algorithm...
User avatar
 
Posts: 3
Joined: Wed Nov 29, 2017 1:51 pm
Location: Comilla University, Comilla, Bangladesh

Re: DCP-381: MULTIPLICATION

by BishalG » Sat Dec 02, 2017 1:59 pm

You may think about dynamic programming.
There will be two transitions:
1.) take and multiply the value at index p.
2.) do not take value at index p.
User avatar
 
Posts: 43
Joined: Tue Jan 17, 2017 10:10 pm

Re: DCP-381: MULTIPLICATION

by Reayz » Sun Dec 03, 2017 10:55 pm

But value can be very large, how to use this value as a state of DP?
User avatar
 
Posts: 3
Joined: Wed Nov 29, 2017 1:51 pm
Location: Comilla University, Comilla, Bangladesh

Re: DCP-381: MULTIPLICATION

by HarryVolde » Tue Dec 05, 2017 2:02 am

You have to find a formula.
Find a formula for fewer elements sets.You can use the formula larger elements sets :D
 
Posts: 1
Joined: Tue Dec 05, 2017 1:56 am

Re: DCP-381: MULTIPLICATION

by BishalG » Tue Dec 05, 2017 9:33 am

You just need to memorize "position" state to determine whether to take value at that position or not.
As the length of array is 1000. You can easily manage that in dp.
User avatar
 
Posts: 43
Joined: Tue Jan 17, 2017 10:10 pm

Re: DCP-381: MULTIPLICATION

by Reayz » Wed Dec 06, 2017 1:55 am

Thanks everyone, including Rajib vai for helping me in this problem. AC...:)
User avatar
 
Posts: 3
Joined: Wed Nov 29, 2017 1:51 pm
Location: Comilla University, Comilla, Bangladesh


Who is online
Users browsing this forum: Bing [Bot] and 1 guest
cron