Day: April 9, 2016

292. Nim Game

fightingminionLeave a comment

Difficulty: Easy

Frequency: N/A

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

Hint:

  1. If there are 5 stones in the heap, could you figure out a way to remove the stones such that you will always be the winner?

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    bool canWinNim(int n) {
        return !(n % 4 == 0);
    }
};

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

 

Things to learn:

189. Rotate Array

fightingminion1 Comment

Difficulty: Easy

Frequency: N/A

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

[show hint]

Hint:
Could you do it in-place with O(1) extra space?

Related problem: Reverse Words in a String II

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        if (n <= 1) return;
        k = k % n;
        vector<int> tmp(nums.begin() + (n - k), nums.end());
        for (int i = 0; i < n - k; i++) {
            tmp.push_back(nums[i]);
        }
        nums = tmp;
    }
};

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

 

Things to learn: