Commit1edd764

committed

edit 357

1 parentcb0f7b0 commit1edd764Copy full SHA for 1edd764

File tree

+12

-0

lines changed

+12

-0

lines changed

Lines changed: 12 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -19,6 +19,18 @@ Let f(k) = count of numbers with unique digits with length equals k.`
`19`	`19`	`*/`
`20`	`20`	`publicclass_357 {`
`21`	`21`
	`22`	`+/**reference: https://discuss.leetcode.com/topic/47983/java-dp-o-1-solution`
	`23`	`+ * Following the hint. Let f(n) = count of number with unique digits of length n.`
	`24`	`+ f(1) = 10. (0, 1, 2, 3, ...., 9)`
	`25`	`+ f(2) = 9 * 9. Because for each number i from 1, ..., 9, we can pick j to form a 2-digit number ij and there are 9 numbers that are different from i for j to choose from.`
	`26`	`+ f(3) = f(2) * 8 = 9 * 9 * 8. Because for each number with unique digits of length 2, say ij, we can pick k to form a 3 digit number ijk and there are 8 numbers that are different from i and j for k to choose from.`
	`27`	`+ Similarly f(4) = f(3) * 7 = 9 * 9 * 8 * 7....`
	`28`	`+ ...`
	`29`	`+ f(10) = 9 * 9 * 8 * 7 * 6 * ... * 1`
	`30`	`+ f(11) = 0 = f(12) = f(13)....`
	`31`	`+ any number with length > 10 couldn't be unique digits number.`
	`32`	`+ The problem is asking for numbers from 0 to 10^n. Hence return f(1) + f(2) + .. + f(n)`
	`33`	`+ As @4acreg suggests, There are only 11 different ans. You can create a lookup table for it. This problem is O(1) in essence.*/`
`22`	`34`	`publicintcountNumbersWithUniqueDigits(intn) {`
`23`	`35`	`if (n ==0) {`
`24`	`36`	`return1;`

Comments

(0)