
问题
给定一个非负整数 num,反复将各个位上的数字相加,直到结果为一位数。
输入: 38
输出: 2
解释: 各位相加的过程为:3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数,所以返回 2。
进阶:
你可以不使用循环或者递归,且在 O(1) 时间复杂度内解决这个问题吗?
Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.
Input: 38
Output: 2
Explanation: The process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.
Follow up:
Could you do it without any loop/recursion in O(1) runtime?
示例
public class Program { public static void Main(string[] args) { var n = 38; var res = AddDigits(n); Console.WriteLine(res); n = 513; res = AddDigits2(n); Console.WriteLine(res); n = 66; res = AddDigits3(n); Console.WriteLine(res); Console.ReadKey(); } private static int AddDigits(int num) { var length = num.ToString().Length; if(length == 1) return num; var res = 0; while(length > 1) { res = 0; for(var i = 0; i < length; i++) { res += int.Parse(num.ToString()[i].ToString()); } num = res; length = num.ToString().Length; } return res; } private static int AddDigits2(int num) { if(num < 10) return num; var temp = num; var sum = 0; while(temp != 0) { sum += temp % 10; temp /= 10; } return AddDigits2(sum); } private static int AddDigits3(int num) { //if(num == 0) return 0; //var result = num % 9; //if(result == 0) return 9; //return result; return num == 0 ? 0 : (num % 9 == 0 ? 9 : num % 9); } }
以上给出3种算法实现,以下是这个案例的输出结果:
2 9 3
分析:
显而易见,AddDigits 和AddDigits2 的时间复杂度为: ,AddDigits3 的时间复杂度为:
。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/3860。