Day 14 (30 Days of Code)

14 July 2023

Today I took it easy just by doing some Leetcode.

What did I learn?

In questions based on Game Theory, all you need to do is to find a path to victory in any way possible.

• Nim Game

My approach:

I struggled with this question until I looked at hints and understood game theory.

My solution:

By analyzing the different test cases it is found that a multiple of 4 is where I lose the game.

class Solution {
public:
    bool canWinNim(int n) {

        if(n%4==0){
            return false;
        }
        return true;
    }
};

• Power of Three

My approach:

This question is very similar to Power of 2 and just like before I was able to solve it in O(logn) time. But when I looked at the solution I saw a smaller approach. However, the time complexity is still O(logn).

My solution:

• First solution

class Solution {
public:
    bool isPowerOfThree(int n) {
        if(n==1){
            return true;
        }
        int count = 0;
        int org = n;
        while(n>1){
            count++;
            n = n/3;
        }

        if(pow(3,count)==org){
            return true;
        }
        return false;
};

• Second solution

class Solution {
public:
    bool isPowerOfThree(int n) {
        if(n==0){
            return false;
        }

        while(n%3==0){
            n = n/3;
        }
        if(n==1){
            return true;
        }
        return false;
    }
};

• Reverse String

My approach:

This question was very easy. To reverse the characters in the string I just used the loop till mid and swap the character of index 'i' & 'size-i-1'.

My solution:

class Solution {
public:
    void reverseString(vector<char>& s) {
        int len = s.size();
        int mid = (len-1)/2;

        for(int i=0;i<=mid;i++){
            swap(s[i],s[len-i-1]);
        }
    }
};

• Reverse Vowels of a String

My solution:

I was able to solve this problem in O(n) time but I was using extra space which made space complexity to O(n). The after a hint realized I can solve this question using Two pointer approach.

My solution:

• Using a Vector

  1. Time Complexity: O(n)

  2. Space Complexity: O(n)

class Solution {
public:
    bool isVowel(char s){
        char arr[] = {'a','e','i','o','u','A','E','I','O','U'};
        for(int i=0;i<10;i++){
            if(s==arr[i]){
                return true;
            }
        }
        return false;
    }
    string reverseVowels(string s) {
        vector<char> v;

        for(int i=s.length()-1;i>=0;i--){
            if(isVowel(s[i])){
                v.push_back(s[i]);
            }
        }

        string output = "";
        int count = 0;
        for(int i=0;i<s.length();i++){
            if(isVowel(s[i])){
                output+=v[count];
                count++;
            }else{
                output+=s[i];
            }
        }

        return output;
    }
};

• Using Two pointer approach:

  1. Time complexity: O(n)

  2. Space complexity: O(1)

class Solution {
public:
    bool isVowel(char s){
        char arr[] = {'a','e','i','o','u','A','E','I','O','U'};
        for(int i=0;i<10;i++){
            if(s==arr[i]){
                return true;
            }
        }
        return false;
    }
    string reverseVowels(string s) {

        int i = 0;
        int j = s.length()-1;

        while(i<j){
            if(!isVowel(s[i])){
                i++;
            }
            else if(!isVowel(s[j])){
                j--;
            }
            else if(i<j){
                swap(s[i],s[j]);
                i++;
                j--;
            }
        }
        return s;
    }
};