Jumping Numbers

Task: Find the all jumping numbers smaller than or equal to given X, Jumping number means a number all adjacent digits differ by 1.

Example:

Input:

1

50

Output:

0 1 2 3 4 5 6 7 8 9 10 12 21 23 32 34 43 45

---

Here is the Code:

Program in C++:

1. #include<iostream>
2. #include<bits/stdc++.h>
3. using namespace std;
4. void jumpingNumbers(int *jd,int n)
5. {
6.     queue<int> q;
7.     jd[0]=0;
8.     int i;
9.     for(i=1;i<10;i++)
10.     {
11.         jd[i]=i;
12.         q.push(i);
13.     }
14.     int num;
15.     while(q.empty()==false&&i<=n)
16.     {
17.         num=q.front();
18.         int t1=num%10;
19.         if(t1==0)
20.         {
21.             jd[i++]=num*10+t1+1;
22.             q.push(jd[i-1]);
23.         }
24.         else if(t1==9)
25.         {
26.             jd[i++]=num*10+t1-1;
27.             q.push(jd[i-1]);
28.         }
29.         else
30.         {
31.             jd[i++]=num*10+t1-1;
32.             q.push(jd[i-1]);
33.             jd[i++]=num*10+t1+1;
34.             q.push(jd[i-1]);
35.         }
36.         q.pop();
37.     }
38. }
39. int main()
40.  {
41. int t;
42. cin>>t;
43. while(t--)
44. {
45.     int n;
46.     cin>>n;
47.     int jd[3500];
48.     jumpingNumbers(jd,3501);
49.     int i=0;
50.     while(jd[i]<=n)
51.     {
52.         cout<<jd[i]<<" ";
53.         i++;
54.     }
55.     cout<<endl;
56. }
57. return 0;
58. }

---

Here is the Video: