wu :: forums - Pick digits in a given number for minimal sum

wu :: forums « wu :: forums - Pick digits in a given number for minimal sum » Welcome, Guest. Please Login or Register. May 15^th, 2024, 3:32am
RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

   wu :: forums
   riddles
   cs (Moderators: Eigenray, towr, ThudnBlunder, Icarus, SMQ, william wu, Grimbal)
   Pick digits in a given number for minimal sum

« Previous topic | Next topic »

Pages: 1

Notify of replies

Send Topic

Author

Topic: Pick digits in a given number for minimal sum (Read 773 times)

Bala69
Newbie

Gender:

Posts: 5

Pick digits in a given number for minimal sum
« on: Aug 31^st, 2011, 6:39am »

Quote

Modify

Can anyone plz give me algorithm for following problem:

Requirements:
Input a single decimal number of arbitrary length.
Treat each digit in the number as a single separate digit. Pick digits from the input so that the sum of your choice is the minimum possible - you can skip *at most* one digit in a row. (If you skip digit n, then digit n+1 must be included in the total).
Print out the input number, the set of numbers added, and the minimum total.
Examples:
Input 2413 Output 2+1=3
Input 111114 Output 1+1+1=3
Input 39915691 Output 9+1+6+1=17
Input 142159119 Output 1+2+5+1+1=10(Note:here you are adding two adjacent digits i.e 1+1)
Note:You can add two adjacent digits but you cant skip two adjacent digits)

IP Logged

Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:

Posts: 7527

Re: Pick digits in a given number for minimal sum
« Reply #1 on: Aug 31^st, 2011, 7:51am »

Quote

Modify

Consider the partial problem of finding the best sum for the first n numbers:
a(n) = smallest possible sum with the first n numbers, including the last digit in the sum,
b(n) = smallest possible sum with the first n numbers, excluding the last digit in the sum.

Can you compute a(1), b(1)?
Can you compute a(n), b(n) from a(n-1),b(n-1)?
Can you compute the best sum overall from the a(n), b(n)?

IP Logged