Yes your formula is right, mine is a bit erroneous.
19thhell
@19thhell
Posts made by 19thhell

RE: My Java solution: find 1 or 7 when happy sum is a single digit

O(n) 8ms C++ method
class Solution { public: int minSubArrayLen(int s, vector<int>& nums) { int start = 0, end = 0, n = nums.size(), min_len = 0, sum = 0; while (end < n) { while (sum < s && end < n) { sum += nums[end++]; } while (sum >= s && start < end) { if (min_len == 0  min_len > end  start) min_len = end  start; sum = nums[start++]; } } return min_len; } };

RE: My Java solution: find 1 or 7 when happy sum is a single digit
Proof to "all numbers' calculation will goes into a single digit at some time". I post this as an answer to have a better format than comment.
The happy sum of a N digit number, Happy(num), will not be larger than Happy(10^(N+1)  1) = 81N.
Therefore when N > 3, we always have 81N < 100N < (10^2) * N < 10^N, that is Happy(num) < num / 10, which will eventually reduce the happy sum of any number to smaller or equal to 999, because Happy(9999) < 999.
Happy(999) = 243, therefore any number larger than 99 and smaller or equal to 999 should have a happy sum smaller or equal to 243, which in turn smaller than 299, which should have the largest happy sum among all numbers in [200, 300).
Happy(299) = 166, therefore Happy(num) will get to a number smaller or equal to 166 at some step, which in turn smaller than 199.
 Happy(199) = 163 < 199.
 Happy(99) = 162.
Combining 1 and 2 above, we know any numbers larger than 100 will be reduced to smaller than 163 at some step, and any numbers smaller than 100 have a happy sum that is smaller or equal to 162, therefore all numbers will be reduced to smaller or equal to 162 at some step.
Now we only have 162 numbers to deal with, you can simply write a program to verify that their happy sum all get to a single digit at some step.

RE: How to prove that comparatorbased solutions are correct?
Let A, B, C be the integer given. To concatenate A and B into AB, we need to know how many digits are there in B, then multiply power of 10 with A, add B to the result. Example: 12312 = 123 * 100 + 12. The number of digits in B is lgB + 1, therefore we need to multiply A with 10^(lgB + 1), then add the result with B to get AB. Now we can start our proof.
Proof: Let us define f(X) = 10^(lgX + 1), then XY = f(Y)X + Y If AB <= BA, then we have f(B)A + B <= f(A)B + A (f(B)  1)A <= (f(A)  1)B that is A <= B·(f(A)  1) / (f(B)  1) (1) If BC <= CB, then we have f(C)B + C <= f(B)C + B (f(C)  1)B <= (f(B)  1)C that is B <= C·(f(B)  1) / (f(C)  1) (2) Combine (1), (2), we have A <= C·(f(A)  1) / (f(C)  1) (f(C)  1)A <= (f(A)  1)C f(C)A + C <= f(A)C + A AC <= CA