Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- int dis[1000005];
- bool vis[1000005];
- class TheSumOfLuckyNumbers
- {
- public:
- vector <int> sum(int n)
- {
- // 1. generate Lucky numbers in a vector
- vector<long long>v;
- vector<int>ans;
- queue<long long>Q;
- Q.push(4);
- Q.push(7);
- while(!Q.empty())
- {
- long long s=Q.front();
- Q.pop();
- if(s<=1000000)
- {
- v.push_back(s);
- }
- long long num=s*10+4;
- if(num<=1000000)
- {
- Q.push(num);
- }
- num=s*10+7;
- if(num<=1000000)
- {
- Q.push(num);
- }
- }
- int sz=v.size();
- //cout<<sz<<endl;
- // 2. calculate distance
- for(int i=0;i<=1000000;i++)dis[i]=0,vis[i]=false;
- queue<int>q;
- q.push(0);
- dis[0]=0;
- vis[0]=1;
- while(!q.empty())
- {
- int u=q.front();
- q.pop();
- for(int i=0;i<sz;i++)
- {
- int nu=u+v[i];
- if(nu>n)break;
- if(!vis[nu])
- {
- vis[nu]=1;
- dis[nu]=dis[u]+1;
- q.push(nu);
- }
- }
- }
- //cout<<dis[n]<<endl;
- // 3. Print solution
- if(!vis[n])return ans;
- for(int i=0;i<sz;i++)
- {
- while(v[i]<=n)
- {
- if(dis[n-v[i]]==dis[n]-1 && vis[n-v[i]] )
- {
- ans.push_back(v[i]);
- n-=v[i];
- }
- else break;
- }
- }
- return ans;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement