{"id":27218,"date":"2018-01-03T22:23:01","date_gmt":"2018-01-03T16:53:01","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27218"},"modified":"2018-01-03T22:23:01","modified_gmt":"2018-01-03T16:53:01","slug":"java-programming-count-n-digit-numbers-whose-sum-digits-equals-given-sum","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-programming-count-n-digit-numbers-whose-sum-digits-equals-given-sum\/","title":{"rendered":"Java Programming &#8211; Count of n digit numbers whose sum of digits equals to given sum"},"content":{"rendered":"<p>Given two integers \u2018n\u2019 and \u2018sum\u2019, find count of all n digit numbers with sum of digits as \u2018sum\u2019. Leading 0\u2019s are not counted as digits.<br \/>\n1 <= n <= 100 and 1 <= sum <= 50000<span id=\"more-135347\"><\/span><\/p>\n<p>Example:<\/p>\n<pre>Input:  n = 2, sum = 2\r\nOutput: 2\r\nExplanation: Numbers are 11 and 20\r\n\r\nInput:  n = 2, sum = 5\r\nOutput: 5\r\nExplanation: Numbers are 14, 23, 32, 41 and 50\r\n\r\nInput:  n = 3, sum = 6\r\nOutput: 21<\/pre>\n<p>The idea is simple, we subtract all values from 0 to 9 from given sum and recur for sum minus that digit. Below is recursive formula.<\/p>\n<pre>    countRec(n, sum) = \u2211countRec(n-1, sum-x)\r\n                            where 0 =< x <= 9 and\r\n                                 sum-x >= 0\r\n\r\n    One important observation is, leading 0's must be\r\n    handled explicitly as they are not counted as digits.\r\n    So our final count can be written as below.\r\n    finalCount(n, sum) = \u2211countRec(n-1, sum-x)\r\n                           where 1 =< x <= 9 and\r\n                                 sum-x >= 0<\/pre>\n[ad type=\u201dbanner\u201d]\n<p>Below is a simple recursive solution based on above recursive formula.<\/p>\n[pastacode lang=\u201djava\u201d manual=\u201dclass%20sum_dig%0A%7B%0A%20%20%20%20%2F%2F%20Recursive%20function%20to%20count%20\u2019n\u2019%20digit%20numbers%0A%20%20%20%20%2F%2F%20with%20sum%20of%20digits%20as%20\u2019sum\u2019.%20This%20function%0A%20%20%20%20%2F%2F%20considers%20leading%200\u2019s%20also%20as%20digits%2C%20that%20is%0A%20%20%20%20%2F%2F%20why%20not%20directly%20called%0A%20%20%20%20static%20int%20countRec(int%20n%2C%20int%20sum)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Base%20case%0A%20%20%20%20%20%20%20%20if%20(n%20%3D%3D%200)%0A%20%20%20%20%20%20%20%20%20%20%20return%20sum%20%3D%3D%200%20%3F1%3A0%3B%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Initialize%20answer%0A%20%20%20%20%20%20%20%20int%20ans%20%3D%200%3B%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Traverse%20through%20every%20digit%20and%20count%0A%20%20%20%20%20%20%20%20%2F%2F%20numbers%20beginning%20with%20it%20using%20recursion%0A%20%20%20%20%20%20%20%20for%20(int%20i%3D0%3B%20i%3C%3D9%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20if%20(sum-i%20%3E%3D%200)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20ans%20%2B%3D%20countRec(n-1%2C%20sum-i)%3B%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20return%20ans%3B%0A%20%20%20%20%7D%0A%20%20%20%20%20%20%0A%20%20%20%20%2F%2F%20This%20is%20mainly%20a%20wrapper%20over%20countRec.%20It%0A%20%20%20%20%2F%2F%20explicitly%20handles%20leading%20digit%20and%20calls%0A%20%20%20%20%2F%2F%20countRec()%20for%20remaining%20digits.%0A%20%20%20%20static%20int%20finalCount(int%20n%2C%20int%20sum)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Initialize%20final%20answer%0A%20%20%20%20%20%20%20%20int%20ans%20%3D%200%3B%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Traverse%20through%20every%20digit%20from%201%20to%0A%20%20%20%20%20%20%20%20%2F%2F%209%20and%20count%20numbers%20beginning%20with%20it%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%201%3B%20i%20%3C%3D%209%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20if%20(sum-i%20%3E%3D%200)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20ans%20%2B%3D%20countRec(n-1%2C%20sum-i)%3B%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20return%20ans%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0A%20%20%20%20public%20static%20void%20main%20(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20int%20n%20%3D%202%2C%20sum%20%3D%205%3B%0A%20%20%20%20%20%20%20%20%20%20System.out.println(finalCount(n%2C%20sum))%3B%0A%20%20%20%20%7D%0A%7D\u201d message=\u201dJava\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Output:<\/p>\n<pre>5<\/pre>\n<p>The time complexity of above solution is exponential. If we draw the complete recursion tree, we can observer that many subproblems are solved again and again. For example, if we start with n = 3 and sum = 10, we can reach n = 1, sum = 8, by considering digit sequences 1,1 or 2, 0.<br \/>\nSince same suproblems are called again, this problem has Overlapping Subprolems property. So min square sum problem has both properties of a dynamic programming problem.<\/p>\n[ad type=\u201dbanner\u201d]\n<p>Below is Memoization based the implementation.<\/p>\n[pastacode lang=\u201djava\u201d manual=\u201dclass%20sum_dig%0A%7B%0A%20%20%20%20%2F%2F%20A%20lookup%20table%20used%20for%20memoization%0A%20%20%20%20static%20int%20lookup%5B%5D%5B%5D%20%3D%20new%20int%5B101%5D%5B50001%5D%3B%0A%20%20%20%20%20%20%0A%20%20%20%20%2F%2F%20Memoizatiob%20based%20implementation%20of%20recursive%0A%20%20%20%20%2F%2F%20function%0A%20%20%20%20static%20int%20countRec(int%20n%2C%20int%20sum)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Base%20case%0A%20%20%20%20%20%20%20%20if%20(n%20%3D%3D%200)%0A%20%20%20%20%20%20%20%20%20%20%20return%20sum%20%3D%3D%200%20%3F%201%20%3A%200%3B%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20this%20subproblem%20is%20already%20evaluated%2C%0A%20%20%20%20%20%20%20%20%2F%2F%20return%20the%20evaluated%20value%0A%20%20%20%20%20%20%20%20if%20(lookup%5Bn%5D%5Bsum%5D%20!%3D%20-1)%0A%20%20%20%20%20%20%20%20%20%20%20return%20lookup%5Bn%5D%5Bsum%5D%3B%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Initialize%20answer%0A%20%20%20%20%20%20%20%20int%20ans%20%3D%200%3B%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Traverse%20through%20every%20digit%20and%0A%20%20%20%20%20%20%20%20%2F%2F%20recursively%20count%20numbers%20beginning%0A%20%20%20%20%20%20%20%20%2F%2F%20with%20it%0A%20%20%20%20%20%20%20%20for%20(int%20i%3D0%3B%20i%3C10%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20if%20(sum-i%20%3E%3D%200)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20ans%20%2B%3D%20countRec(n-1%2C%20sum-i)%3B%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20return%20lookup%5Bn%5D%5Bsum%5D%20%3D%20ans%3B%0A%20%20%20%20%7D%0A%20%20%20%20%20%20%0A%20%20%20%20%2F%2F%20This%20is%20mainly%20a%20wrapper%20over%20countRec.%20It%0A%20%20%20%20%2F%2F%20explicitly%20handles%20leading%20digit%20and%20calls%0A%20%20%20%20%2F%2F%20countRec()%20for%20remaining%20n.%0A%20%20%20%20static%20int%20finalCount(int%20n%2C%20int%20sum)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Initialize%20all%20entries%20of%20lookup%20table%0A%20%20%20%20%20%20%20%20for(int%20i%20%3D%200%3Bi%3C%3D100%3B%2B%2Bi)%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20for(int%20j%3D0%3Bj%3C%3D50000%3B%2B%2Bj)%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20lookup%5Bi%5D%5Bj%5D%20%3D%20-1%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Initialize%20final%20answer%0A%20%20%20%20%20%20%20%20int%20ans%20%3D%200%3B%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Traverse%20through%20every%20digit%20from%201%20to%0A%20%20%20%20%20%20%20%20%2F%2F%209%20and%20count%20numbers%20beginning%20with%20it%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%201%3B%20i%20%3C%3D%209%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20if%20(sum-i%20%3E%3D%200)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20ans%20%2B%3D%20countRec(n-1%2C%20sum-i)%3B%0A%20%20%20%20%20%20%20%20return%20ans%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0A%20%20%20%20public%20static%20void%20main%20(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20int%20n%20%3D%202%2C%20sum%20%3D%205%3B%0A%20%20%20%20%20%20%20%20%20%20System.out.println(finalCount(n%2C%20sum))%3B%0A%20%20%20%20%7D%0A%7D\u201d message=\u201dJava\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Output:<\/p>\n<pre>5<\/pre>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Java Programming &#8211; Count of n digit numbers whose sum of digits equals to given sum &#8211; Dynamic Programming Given two integers \u2018n\u2019 and \u2018sum\u2019, find count<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,70145,2139],"tags":[81124,81122,81123,72842,72846,72850,72839,81132,81128,81119,72852,81131,72855,81129],"class_list":["post-27218","post","type-post","status-publish","format-standard","hentry","category-coding","category-dynamic-programming","category-java","tag-a-problem-from-a-programming-competition","tag-advanced-algorithms-practice-problems","tag-count-of-numbers-between-a-and-b-inclusive-that-have-sum-of-digits","tag-define-dynamic-programming","tag-dynamic-programming-in-data-structure","tag-explain-dynamic-programming","tag-how-to-solve-dynamic-programming-problems","tag-number-of-occurrences-of-the-digit-1-in-the-numbers-from-0-to-n","tag-numbers-of-length-n-and-value-less-than-k","tag-print-all-n-digit-numbers-whose-sum-of-digits-equals-to-given-sum","tag-problems-on-dynamic-programming","tag-program-to-find-sum-of-digits-of-a-number-in-c","tag-simple-dynamic-programming-example","tag-sum-of-digits-from-1-to-100"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27218","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27218"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27218\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27218"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27218"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27218"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}