Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <queue>
- using namespace std;
- // It's like a BFS algorithm, where you have 9 roots for 9 trees (1, 2, ..., 9).
- // For each tree, you scan it level by level,
- // and you generate the two children of every number,
- // add them to the queue, and remove the current number at q.front().
- // When you generate a children, make sure that the digit is >= 0 and <= 9.
- // So, If currNum = 9, therefore, two possible children 9[8] (valid) and 9[10] (invalid).
- // This algorithm will take O(10 * LogN), where Log is to the base 10. Because in every tree level we multiply by 10.
- int main() {
- int t;
- scanf("%d",&t);
- while(t--) {
- long long n;
- scanf("%lld",&n);
- if(n <= 9) {
- printf("%d\n", -1); continue;
- }
- queue<long long> q;
- for(int i = 1; i <= 9; i++)
- q.push(i);
- while(true) {
- long long currNum = q.front();
- int lastDigit = currNum % 10;
- if(currNum > n)
- break;
- else if(currNum > 9 && currNum <= n)
- printf("%lld ", currNum);
- if(lastDigit - 1 >= 0){
- q.push(currNum * 10 + (lastDigit - 1));
- }
- if(lastDigit + 1 <= 9){
- q.push(currNum * 10 + (lastDigit + 1));
- }
- q.pop();
- }
- printf("\n");
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment