Cracking the Code: My Epic DSA Journey in 21 Days

My Introduction

So this is Kush Munot and I am a 3rd-year Undergrad from Shri Ramdeobaba College Of Engineering and Management, Nagpur. I am a Full Stack Developer and I use React.js, Next.js, Material UI, and Tailwind CSS in the frontend part and prefer to use Node.js and REST APIs in the Backend. Apart from this I also like to contribute to the Community side, I am a Postman Student Leader and take Sessions on API development and Testing. I am also the Chapter Lead of the GFG RCOEM Chapter, where we conduct various events on different technologies.

Day 01 - 15 June 2023

So I had my exams today but still striving to solve questions and start this challenge.

Question 01 - Print first n Fibonacci Numbers

The Question states that Given a number N, find the first N Fibonacci numbers. The first two numbers of the series are 1 and 1.

Example 1:

Input:
N = 5
Output: 1 1 2 3 5

Came up with a simple solution using for loops

    vector<long long> printFibb(int n) 
    {
        vector<long long> ans;
        ans.push_back(1);
        ans.push_back(1);
        for(int i=2;i<n;i++){
            ans.push_back(ans[i-2]+ans[i-1]);
        }
        return ans;

    }

But this fails for a small condition where input is 1 hence modifying the code for this case

    vector<long long> printFibb(int n) 
    {
        vector<long long> ans;
        if(n == 1)
            ans.push_back(1);
        else{
            ans.push_back(1);
            ans.push_back(1);
            for(int i=2;i<n;i++){
                ans.push_back(ans[i-2]+ans[i-1]);
            }
            return ans;
        }
    }

It is a simple piece of code that pushes 1,1 in the and vector and adds the previous two numbers i.e. ans[i-2]+ans[i-1] and stores it as 3rd element. ( This is what Fibonacci is actually 😂)

Question 02 - Majority Element

Given an array A of N elements. Find the majority element in the array. A majority element in an array A of size N is an element that appears more than N/2 times in the array.

    int majorityElement(int arr[], int n)
    {
        int ans = 0;
        map<int,int>mp;
        for(int i=0;i<n;i++){
            mp[arr[i]]++;
        }
        map<int,int>::iterator it;
        int x = n/2;
        for(it = mp.begin(); it!= mp.end();it++){
            if(it->second >= x+1){
                ans = it->first;
            }
        }
        if(ans == 0)
            ans = -1;

        return ans;        
    }

The logic behind this is simply that you store frequencies of the element in a map data structure then calculate the x/2 value and see if the frequency is greater than x/2 or not if it is then we update the answer variable and return the answer.

Question 03 - Next Permutation

This was relatively tough question because it was giving TLE on naive approach. I wasn't able to think the optimized approach so I had to see the solution video but learnt a new concept through it too.

vector<int> nextPermutation(int n, vector<int> a){
        int i = n-1;        
        while(i > 0 && a[i-1] >= a[i])
            i--;

        reverse(a.begin()+i, a.end());        
        if(i != 0) {
            int x = i-1;
            while(i < n && a[i] <= a[x])
                i++;                
            swap(a[i], a[x]);                
        }        
        return a;    
    }

That beautifully explained the approach here do check it out !!

That's all for today
See yaa tomorrow. If you guys wanna connect make sure you hit me a Hiii on any of these platforms. Let's Connect !!

#coding #codinglife #codingisfun #codingbootcamp #codingdays #learncoding #coding #codinglife #codingisfun #codingbootcamp #codingdays #learncoding #gfg #leetcode #21daysofcode