Good morning! Here’s your coding interview problem for today.
This problem was asked by Microsoft.
A number is considered perfect if its digits sum up to exactly 10.
Given a positive integer n, return the n-th perfect number.
For example, given 1, you should return 19. Given 2, you should return 28.
题目意思：所谓perfect number ，指一个正整数，如果这个数的每一位数字加起来等于10。第一个perfect number是19 （1+9=10），第二个是28（2+8=10）。要求你写个函数能够返回第n个perfect number。
solution：
方法一：暴力查找
直接从start=19开始计算，每次判断下是否为完美数字，如果是，则count++ ，然后start+1，进行下次判断。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
/** * 暴力查找的方式 * * @param nth * @return */ public static List<Integer> findNthMethod1List(int nth) { List<Integer> list = new ArrayList<>(nth); int start = 19; int count = 0; while (count <= nth) { int temp = start; int sum = 0; while (temp != 0) { sum = temp % 10 + sum; temp = temp / 10; } if (sum == 10) { list.add(start); count++; } start++; } return list; } |
方法二：增加步长，提高效率
方法一中start++的方式，比较慢。我们可以每次start= start+9 ，这样会快很多。如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
public static int findNthMethod2(int n) { int count = 0; for (int curr = 19; ; curr += 9) { // Find sum of digits in current no. int sum = 0; for (int x = curr; x > 0; x = x / 10) { sum = sum + x % 10; } // If sum is 10, we increment count if (sum == 10) { count++; } // If count becomes n, we return current // number. if (count == n) { return curr; } } } |
注意：
1.这里虽然每次可以+9，但是有个问题，比如假设到271， 280， 下一个完美数就并不是289。网上不少人写的算法有这个问题，认为可以直接通过n而不需要count变量来得到第n个完美数。这就是问题的关键点，我们找不到一个公式将完美数与n直接关联上，必须通过count来计数，从count=0一直累加到count= n。否则，我们只能保证算法返回的是完美数，但是这个数很可能并不是第n个。原文的方法三就是个错误的算法，我在最后面的测试代码中有对比。
2.步长不仅可以是9，其实也可以是10。从0开始，每次加10，此时start=10 ，start/10=1， 此时每个位数字和位1，则末尾就是10-1=9，第一个完美数就是19， start=19+10 , 29/10=2 ，则末尾就是10-2=8 ，第二个完美数就是28。如果上一个完美数是280，则（280+10）/10=29 ， 2+9>10 ， 所以继续加10：290+10=300 ，300/10=30 ，则末尾就是10-3-0=7 ，这个完美数就是307 ，依次类推。这里9比10好，就是因为加9刚好让低位减少1，高位+1，再大多数情况下，+9都能直接得到完美数，不用再推算最后一位的值。
下面是完整的代码，增加了对数器来用生成测试用例，检测算法是否正确：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 |
package testAlgorithms; import java.util.ArrayList; import java.util.List; public class FindPerfectNumberTest { public static void main(String[] args) { System.out.println(isPerfect(18)); System.out.println(isPerfect(28)); System.out.println("checkAlgorithm:" + checkAlgorithm(10000)); } /** * 检测算法是否正确 * * @param nth * @return */ public static boolean checkAlgorithm(int nth) { long startTime = System.currentTimeMillis(); // List<Integer> myList = findNthMethod2List(nth); // List<Integer> myList = findNthMethod3List(nth); List<Integer> myList = findNthErrMethodList(nth); long endTime = System.currentTimeMillis(); System.out.println(" effective method use time :" + ( endTime-startTime)); startTime = System.currentTimeMillis(); List<Integer> correctList = findNthMethod1List(nth); // List<Integer> correctList = findNthMethod3List(nth); endTime = System.currentTimeMillis(); System.out.println(" bruce method use time :" + (endTime-startTime)); for (int i = 0; i < myList.size(); i++) { if (!myList.get(i).equals(correctList.get(i))) { System.out.println("myList: " + myList); System.out.println("correctList: " + correctList); System.out.println("wrong nth:" + (i + 1) + " ; my: " + myList.get(i) + " ; correct : " + correctList.get(i)); return false; } } return true; } /** * 暴力查找的方式 * * @param nth * @return */ public static int findNthMethod1(int nth) { int start = 19; int count = 0; while (count <= nth) { int temp = start; int sum = 0; while (temp != 0) { sum = temp % 10 + sum; temp = temp / 10; } if (sum == 10) { count++; return start; } start++; } return start; } /** * 暴力查找的方式 * * @param nth * @return */ public static List<Integer> findNthMethod1List(int nth) { List<Integer> list = new ArrayList<>(nth); int start = 19; int count = 0; while (count <= nth) { int temp = start; int sum = 0; while (temp != 0) { sum = temp % 10 + sum; temp = temp / 10; } if (sum == 10) { list.add(start); count++; } start++; } return list; } public static boolean isPerfect(int value) { int sum = 0; while (value != 0) { sum = value % 10 + sum; value = value / 10; } if (sum == 10) { return true; } return false; } /** * 步长为9 * @param n * @return */ public static int findNthMethod2(int n) { int count = 0; for (int curr = 19; ; curr += 9) { // Find sum of digits in current no. int sum = 0; for (int x = curr; x > 0; x = x / 10) { sum = sum + x % 10; } // If sum is 10, we increment count if (sum == 10) { count++; } // If count becomes n, we return current // number. if (count == n) { return curr; } } } public static List<Integer> findNthMethod2List(int n) { List<Integer> list = new ArrayList<>(n); int count = 0; for (int curr = 19; ; curr += 9) { // Find sum of digits in current no. int sum = 0; for (int x = curr; x > 0; x = x / 10) { sum = sum + x % 10; } // If sum is 10, we increment count if (sum == 10) { list.add(curr); count++; } // If count becomes n, we return current // number. if (count == n) { return list; } } } /** * 步长为10的 * @param n * @return */ public static List<Integer> findNthMethod3List(int n) { List<Integer> list = new ArrayList<>(n); int count = 0; for (int curr = 0; ; curr += 10) { // Find sum of digits in current no. int sum = 0; int temp = curr/10; for (int x = curr/10; x > 0; x = x / 10) { sum = sum + x % 10; } if(sum > 10 ||sum == 0){ continue; }else { int left = 10 - sum; list.add(temp*10+left); count++; } // If count becomes n, we return current // number. if (count == n) { return list; } } } /** * Error Method ，wrong algorithm * @param n * @return */ public static int findNthErrMethod(int n) { int nthElement = 19 + (n - 1) * 9; int outliersCount = (int)Math.log10(nthElement) - 1; // find the nth perfect number nthElement += 9 * outliersCount; return nthElement; } /** * Error Method ，wrong algorithm * @param n * @return */ public static List<Integer> findNthErrMethodList(int n) { List<Integer> list = new ArrayList<>(n); for (int i = 1; i <= n ;i++){ list.add(findNthErrMethod(i)); } return list; } } |
转载请注明：大步's Blog » Is Perfect Number 完美数（esay）