38.md

Recamans Sequence

Method 1 (TLE)

vector<int> recamanSequence(int n){
        // code here
        
        vector<int>ans(n,0); 
        
        for(int i=1;i<n;i++)
        {
            if((ans[i-1]-i)>0 && find(ans.begin(), ans.end(), (ans[i-1]-i))==ans.end())
                ans[i]=ans[i-1]-i;
            else
                ans[i]=ans[i-1]+i;
        }
        return ans;
    }

Method 2

vector<int> recamanSequence(int n){
        // code here
        
        vector<int>ans(n,0);
        unordered_map<int,int>m;
        m[0]=0;
        
        
        for(int i=1;i<n;i++)
        {
            int x=ans[i-1]-i;
            if((x)>0 &&m[x]==0)
            {
                ans[i]=x;
                m[x]=1;
            }
            else
            {
                ans[i]=ans[i-1]+i;
                m[ans[i-1]+i]=1;
            }
        }
        return ans;
    }