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，进行下次判断。
/**
* 暴力查找的方式
*
* @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 ，这样会快很多。如下：
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都能直接得到完美数，不用再推算最后一位的值。
下面是完整的代码，增加了对数器来用生成测试用例，检测算法是否正确：
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;
}
}