2582. Pass the Pillow

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int passThePillow(int n, int time) {
        // 1-2-3-4-3-2-1-2-3-4
        // pattern is 1-2-3-4-3-2
        vector<int> lines;
        for(int i=1;i<=n;++i) lines.push_back(i);
        for(int i=n-1;i>1 ;i--) lines.push_back(i);
        return lines[time%(2*n-2)];      
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int passThePillow(int n, int time) {
        // 1-2-3-4-3-2-1-2-3-4
        // pattern is 1-2-3-4-3-2
        // vector<int> lines;
        // for(int i=1;i<=n;++i) lines.push_back(i);
        // for(int i=n-1;i>1 ;i--) lines.push_back(i);
        // return lines[time%(2*n-2)];   
        time%=(2*n-2);
        if(time > n-1 ) return n-time%(n-1);
        else return time+1;
    }
};

analysis

  • time complexity O(n) could lower to O(1)
  • space complexity O(n) could lower to O(1)