nikunjsoni

932

Jul 28th, 2021
608
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     unordered_map<int, vector<int>> memo;
  4.     vector<int> beautifulArray(int n) {
  5.         return solve(n);
  6.     }
  7.    
  8.     vector<int> solve(int n){
  9.         if(memo.count(n))
  10.             return memo[n];
  11.        
  12.         vector<int> ans;
  13.         if(n == 1){
  14.             ans.push_back(1);
  15.         }
  16.         else{
  17.             // Have all odd integers on left.
  18.             for(int num: solve((n+1)/2))
  19.                 ans.push_back(2*num-1);
  20.            
  21.             // Have all even integers on right.
  22.             for(int num: solve(n/2))
  23.                 ans.push_back(2*num);
  24.         }
  25.         memo[n] = ans;
  26.         return ans;
  27.     }
  28. };
RAW Paste Data