[JAVA] For if else lovers
Strategy\nWe\'re taking the problem, slice it into smaller bites, solve for the smaller bites, and\nadd up what we calculate in each slice. \n\nSolution\nImagin
**Strategy**\nWe\'re taking the problem, slice it into smaller bites, solve for the smaller bites, and\nadd up what we calculate in each slice. \n\n**Solution**\nImagine we have three digits, x, y, and z. There are multiple ways to have a permutation\nof these digits such that at least one of the digits is repeated. Let\'s not solve for that.\nInstead we solve for permutations w/o repeated digits. The idea is for index 0 we have\nthree digits to choose from, x, y, and z. For index 1 we only have two choices left since\none choice has already been exhausted when we picked a digit for index 0. It doesn\'t\nmatter which digit we choose at what index. What matters is the number of choices we\nhave at each index.\n\n**Example 1**\nLet\'s say we\'re calculating the number of permutations w/o repeated digits and lower\nthan 1000. Let\'s slice our problem into smaller problems. We don\'t care about the\nvalue of 1000 at this point. We say 1000 is consisting of four digits. We solve the\noriginal problem for numbers lower than 9 (one 9), lower than 99 (two 9\'s), and lower\nthan 999 (three 9\'s). We know that not all four digit numbers are lower than 1000 so\nwe won\'t solve for numbers lower than 9999 (four 9\'s). We\'ll take care of four digits\nnumbers later. Solving for numbers consisting of 9\'s is easy. Let\'s explain what happens\nnext in Example 2.\n\n**Example 2**\nLet\'s say we\'re solving for 1,534,634. Plan is to slice it into smaller problems. Let\'s\nsay we already solved for numbers up to 999,999 like what we explained in Example 1.\nFor 1,000,000 to 1,534,634 our smaller problems are solving for 1,499,999 plus solving\nfor 1,500,000 all the way to 1,534,634. The latter piece will be sliced into smaller \nproblems as well. Smaller problems from 1,500,000 to 1,534,634 are solving for the \nfollowings,\nsolving for 1,529,999 plus\nsolving for 1,533,999 plus\nsolving for 1,534,599 plus\nsolving for 1,534,629 plus\nsolving for 1,534,634.\nIn each iteration we keep track of a pointer which is a pivot pointer. All digits \nbefore pivot represent themselves, so the possibilities for each is always one.\nThe pivot digit can take any digit up to the value of the pivot digit minus all \npossibilities that we\'ve already exhausted.\nLet\'s say we\'re dealing w/ 1,529,999 and pivot is at index 2 meaning starting from\nleft first digit is 1 and represents itself b/c it\'s before pivot. Second digit is\n5 and represents itself for the same reason. Now digit 2 is our pivot digit. We say\nour possibilities are 0, 1, and 2 so three possibilities but we have already exhausted\none of our possibilities which is 1 at index 0. So we\'re left w/ only two possibilities\nand again 1 and 5 represent themselves and 2 is lower than 5 so the only exhausted\npossibility is 1. For all those 9\'s after pivot we say possibilities are 0 to 9 which\nis 10 possibilities minus the count of exhausted possibilities, so in this case for\nthe first 9 we have 10-3=7 possibilities, for the second 9 we have 6 possibilities and \nso on.\nAdd up all counts from each iteration and we have all permutations w/o repeated digits.\nSubtract the total count from the original input number and we have all permutations\nw/ at least one repeated digit.\n```\nimport java.util.HashSet;\n\nclass Solution {\n\tint noRepeatCount = 0;\n\n\tpublic int numDupDigitsAtMostN(int n) {\n\t\tint nStrLength = String.valueOf(n).length();\n\t\tint allNineLength = 0;\n\n\t\t// Edge cases out of the way.\n\t\tif (n < 0 || nStrLength < 2)\n\t\t\treturn 0;\n\t\t\n\t\t// If n is all 9\'s like 99999.\n\t\telse if (Math.pow(10, nStrLength) - 1 == n)\n\t\t\tallNineLength = nStrLength;\n\t\t\n\t\t// If n is not all 9\'s we calculate the largest number lower than n consisting of all 9\'s.\n\t\telse\n\t\t\tallNineLength = nStrLength - 1;\n\n\t\t// Calculating all 9\'s e.g. for 10^6 we calculate for six 9\'s which is 999,999.\n\t\tfor (int numberOfDigits = 1; numberOfDigits <= allNineLength; numberOfDigits++) {\n\t\t\tnoRepeatCount += calcNumberOfNoRepeat(numberOfDigits);\n\t\t}\n\n\t\t// Calculating from all 9\'s to n e.g. for 10^6 we already calculated up to 999,999 and\n\t\t// we just need to calculate for the rest.\n\t\tif (Math.pow(10, nStrLength) - 1 > n) {\n\t\t\t\n\t\t\t// Count of all possible values 0 to 9.\n\t\t\tint mutations = 10;\n\t\t\t\n\t\t\t// HashSet is used only in part of the code. Worst case size() is the number of\n\t\t\t// mutations. contains() is called nStrLength times worst case in each iteration\n\t\t\t// w/ no more than nStrLength iterations.\n\t\t\tHashSet<Integer> hs = new HashSet<>();\n\t\t\t\n\t\t\t// We have two pointers each nStrLength hops to travel.\n\t\t\t// index1 is the pivot index and index2 keeps track of the current digit in n.\n\t\t\t// Based on index1 we decide what to do w/ digit at index2.\n\t\t\tfor (int index1 = 0; index1 < nStrLength; index1++) {\n\t\t\t\t\n\t\t\t\t// In each iteration we count noRepeat numbers. At the end of the iteration\n\t\t\t\t// we add local noRepeat count to the total noRepeat count.\n\t\t\t\tint noRepeatCountLocal = 0;\n\t\t\t\t\n\t\t\t\t// Digits visited in each iteration have nothing to do w/ other iterations\n\t\t\t\t// so we clear the HashSet before start of each inner iteration.\n\t\t\t\ths.clear();\n\t\t\t\tfor (int index2 = 0; index2 < nStrLength; index2++) {\n\t\t\t\t\t// Extracting digit at index2.\n\t\t\t\t\tint index2Digit = (int) (n / Math.pow(10, String.valueOf(n).length() - (index2 + 1)) % 10);\n\t\t\t\t\t// index1 is the pivot. Anything before index1 is already taken care of.\n\t\t\t\t\t// This means digits before index1 can only represent themselves, which\n\t\t\t\t\t// means if we see duplicate digits before index1 noRepeatCountLocal\n\t\t\t\t\t// for that entire iteration becomes zero. Remember we\'re counting numbers\n\t\t\t\t\t// w/o repeated digits.\n\t\t\t\t\tif (index2 < index1) {\n\t\t\t\t\t\t// This is where we use HashSet. If digit at index2 is already in the\n\t\t\t\t\t\t// HashSet that means we\'re dealing w/ a duplicate so noRepeatCountLocal\n\t\t\t\t\t\t// is set to zero and we\'re done w/ the iteration.\n\t\t\t\t\t\tif (hs.contains(index2Digit)) {\n\t\t\t\t\t\t\tnoRepeatCountLocal = 0;\n\t\t\t\t\t\t\tbreak;\n\t\t\t\t\t\t} else\n\t\t\t\t\t\t\t// If digit at index2 is not part of the HashSet add it to the HashSet.\n\t\t\t\t\t\t\ths.add(index2Digit);\n\t\t\t\t\t// index2 is meeting the pivot digit. The idea is to subtract 1 from the pivot\n\t\t\t\t\t// digit and make a possible big jump depending on the position of index1.\n\t\t\t\t\t// Imagine we\'re dealing w/ 15,564,465. The idea is to count for 14,xxx,xxx. \n\t\t\t\t\t// We\'ll replace those x\'s w/ 9\'s later in the code. So basically we skip over\n\t\t\t\t\t// 10^7-1 to 1.5*10^7-1.\n\t\t\t\t\t} else if (index2 == index1) {\n\t\t\t\t\t\t// Special case when both pointers are at index 0 meaning we\'re dealing w/\n\t\t\t\t\t\t// the first digit of n, which can\'t be 0.\n\t\t\t\t\t\tif (index2 == 0) {\n\t\t\t\t\t\t\tnoRepeatCountLocal = index2Digit - 1;\n\t\t\t\t\t\t} else {\n\t\t\t\t\t\t\tint inIndex2Range = 0;\n\t\t\t\t\t\t\t// Any digit before digit at index2 and larger than digit at index2\n\t\t\t\t\t\t\t// has no effect on digit at index2. Imagine digit at index2 is 5 \n\t\t\t\t\t\t\t// and digits before that are 8 and 9. Plan is to subtract 1 from 5 and\n\t\t\t\t\t\t\t// pad w/ 9\'s, which gives us 8949999... Knowing that pivot is at 4 and\n\t\t\t\t\t\t\t// 8 and 9 represent themselves, digit at index2 can potentially be any\n\t\t\t\t\t\t\t// value from 0 to 4, which are all less than 8 and 9. As a result 8 \n\t\t\t\t\t\t\t// and 9 have no effect on possible digits at index2. Now if we had 1 \n\t\t\t\t\t\t\t// and 2 instead of 8 and 9 then the possible values for digit at index2\n\t\t\t\t\t\t\t// would be 0, 3, and 4 since 1 and 2 are already used before index2.\n\t\t\t\t\t\t\t// There\'s a special case though when index2 points to the last digit,\n\t\t\t\t\t\t\t// in which we don\'t subtract 1 and we don\'t pad with 9\'s.\n\t\t\t\t\t\t\t// After the first if statement we have a count of all exhausted possible\n\t\t\t\t\t\t\t// values to subtract from all possible values for digit at index2.\n\t\t\t\t\t\t\tfor (int j : hs) {\n\t\t\t\t\t\t\t\tif ((index2 < nStrLength - 1 && j <= index2Digit - 1)\n\t\t\t\t\t\t\t\t\t\t|| (index2 == nStrLength - 1 && j <= index2Digit))\n\t\t\t\t\t\t\t\t\tinIndex2Range++;\n\t\t\t\t\t\t\t}\n\t\t\t\t\t\t\tif (index2 == nStrLength - 1)\n\t\t\t\t\t\t\t\tnoRepeatCountLocal = index2Digit + 1 - inIndex2Range;\n\t\t\t\t\t\t\telse\n\t\t\t\t\t\t\t\tnoRepeatCountLocal = index2Digit - inIndex2Range;\n\t\t\t\t\t\t}\n\t\t\t\t\t// Working on 9\'s like in 123,999,999. Possible values for each 9 is 10\n\t\t\t\t\t// for 0 to 9. Actual possible values however are possible values at each\n\t\t\t\t\t// index minus exhausted possible values at that index.\n\t\t\t\t\t} else {\n\t\t\t\t\t\tnoRepeatCountLocal *= mutations - index2;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t\t// Inner for is done. Adding whatever we\'ve calculated to the total count.\n\t\t\t\tif (noRepeatCountLocal > 0)\n\t\t\t\t\tnoRepeatCount += noRepeatCountLocal;\n\t\t\t}\n\t\t}\n\t\t// Now we have count of permutations w/o repeated digits. Subtracting from n gives\n\t\t// count of permutations <= n w/ at least one repeated digit.\n\t\treturn n - noRepeatCount;\n\t}\n\n\t// Helper function to calculate count of permutations w/o repeated digits. Input is the\n\t// number of 9\'s to be accounted for. \n\tpublic int calcNumberOfNoRepeat(int numberOfDigits) {\n\t\tint noRepeatCount = 0;\n\t\tint mutations = 9;\n\t\tfor (int i = 0; i < numberOfDigits; i++) {\n\t\t\tif (i == 0)\n\t\t\t\tnoRepeatCount = mutations;\n\t\t\telse {\n\t\t\t\tnoRepeatCount *= mutations--;\n\t\t\t}\n\t\t}\n\t\treturn noRepeatCount;\n\t}\n}\n```
['Probability and Statistics', 'Java']