How to Convert Integer to the Sum of Two No-Zero Integers?
- 时间:2020-09-12 10:06:27
- 分类:网络文摘
- 阅读:100 次
Given an integer n. No-Zero integer is a positive integer which doesn’t contain any 0 in its decimal representation.
Return a list of two integers [A, B] where:
A and B are No-Zero integers.
A + B = n
It’s guarateed that there is at least one valid solution. If there are many valid solutions you can return any of them.Example 1:
Input: n = 2
Output: [1,1]
Explanation: A = 1, B = 1. A + B = n and both A and B don’t contain any 0 in their decimal representation.
Example 2:Input: n = 11
Output: [2,9]
Example 3:Input: n = 10000
Output: [1,9999]
Example 4:Input: n = 69
Output: [1,68]
Example 5:Input: n = 1010
Output: [11,999]Constraints:
2 <= n <= 10^4Hints:
Loop through all elements from 1 to n.
Choose A = i and B = n – i then check if A and B are both No-Zero integers.
Bruteforce Algorithm to Convert an Integer to Two NonZero Sum
The bruteforce algorithm is intuitive solution that we can use to check the first integer range from 1 to n – 1, then we need to check both numbers if they contain zeros.
To check if a integer has zeros in it, one approach would be to convert it to string. For example, in C++, we can use std::to_string() to convert a integer to std::string. Alternatively, we can check the rightmost (least significant) digit and divide by ten repeatedly.
Below are the bruteforce implementations of C++, Python and Java respectively.
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | class Solution { public int[] getNoZeroIntegers(int n) { for (int i = 1; i < n; ++ i) { int a = i; int b = n - a; if (nozeros(a) && nozeros(b)) { return new int[]{a, b}; } } return null; } private boolean nozeros(int x) { while (x > 0) { if (x % 10 == 0) return false; x /= 10; } return true; } } |
class Solution { public int[] getNoZeroIntegers(int n) { for (int i = 1; i < n; ++ i) { int a = i; int b = n - a; if (nozeros(a) && nozeros(b)) { return new int[]{a, b}; } } return null; } private boolean nozeros(int x) { while (x > 0) { if (x % 10 == 0) return false; x /= 10; } return true; } }
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | class Solution { public: vector<int> getNoZeroIntegers(int n) { for (int i = 1; i < n; ++ i) { if (nonzeros(i) && nonzeros(n - i)) { return {i, n - i}; } } return {}; } private: bool nonzeros(int n) { while (n > 0) { if (n % 10 == 0) return false; n /= 10; } return true; } }; |
class Solution { public: vector<int> getNoZeroIntegers(int n) { for (int i = 1; i < n; ++ i) { if (nonzeros(i) && nonzeros(n - i)) { return {i, n - i}; } } return {}; } private: bool nonzeros(int n) { while (n > 0) { if (n % 10 == 0) return false; n /= 10; } return true; } };
Python
1 2 3 4 5 6 | class Solution: def getNoZeroIntegers(self, n: int) -> List[int]: a = 1 while '0' in f'{a}{n-a}': a += 1 return [a, n - a] |
class Solution: def getNoZeroIntegers(self, n: int) -> List[int]: a = 1 while '0' in f'{a}{n-a}': a += 1 return [a, n - a]
The following is interesting as we are using the generator to yield the first (next) valid solution.
1 2 3 | class Solution: def getNoZeroIntegers(self, n: int) -> List[int]: return next([a, n - a] for a in range(1, n) if not '0' in f'{a}{n - a}') |
class Solution: def getNoZeroIntegers(self, n: int) -> List[int]: return next([a, n - a] for a in range(1, n) if not '0' in f'{a}{n - a}')
All the above implementations run at O(N) time and O(1) constant space.
We can also use two pointers starting at both ends towards each other, and the complexity will be the same.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:问题“毒皮蛋”再引食品安全大讨论 教你六招辨别保健食品真假的方法 警惕保健食品的五大非法宣传“陷阱” 官员竟然称质疑转基因食品是民众无知 转基因食品的利与弊及潜在危害浅析 食品安全法即将修订 有奖举报或将入法 辽宁省曝光十大食品犯罪典型案例 几种转基因与非转基因食物的差别 判断是否为转基因食品的简单方法 转基因食品与肿瘤等高度相关引关注
- 评论列表
-
- 添加评论