Two Pointers Technique & Binary Search For Beginners

Problem: TOPCODER SRM 403 :  TheSumOfLuckyNumbers 

Statement: we have to say can we get N by adding lucky numbers as minimum as possible.. :)

Facts:
1.There are only 1022 lucky numbers from 1 to 10^9 and only 126 from 1 to10^6. :)
Solution: 

1.first generate vector of lucky numbers using BFS. for eg: LUCKY NUM GENERATION

2.Then, again one BFS to calculate minimum distance of number using lucky numbers .

3. then Print the required solution using iterative for loop & while condition !!

That's it.

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;
    }
};
 LINK:here