-->

October 2020

My Blog

Latest blog

 

Difference Array  algorithm udating range query the cs engineer



Intro :

So, recently I was solving a problem on CodeForces and I was not able to do it which is pretty common and mainly because I did not know about this algorithm and thus I read a bunch of editorials and then I found out about something called difference array and it's pretty basic and easy algorithm but makes increasing the values of a range of elements in an array a lot easier and specifically it reduces the update time from linear O(n) to constant O(1).

So, we will be learning the algorithm by understanding it first and the implementing later as I have provided the code for the implementation of the algorithm .

What do Difference Arrays do ?:

  Imagine there if the user gives a command like update(l,r,x). And the user wants that in the given array, all the elements within the position 'l' in the left to 'r' in the right, get increased by x .This algorithm updates the queries in constant time O(1). 

Naive/Simple Algorithm :

 So, by reading the question what comes into our mind first is that we will just traverse the array from l to r position most probably in a for loop and add x to all the numbers coming in the way .

But, what if the user gives a lot of queries then imagine every time going through the loop for each time we get a query is pretty tedious and we just want to do it fast. 

Now enters Difference arrays which handles each query in a constant time and at last we just traverse the array once while printing the resulting array after updating our array on a lot queries .


Time Complexity : O(1) for updating but just printing the array  takes O(n).

 The Idea :

        So, the idea of the algorithm is simply that we make a new array which stores the difference of the adjacent elements in the original array . And for each query we make a few changes in constant time that results in an updated array after all the queries are worked upon.

Understanding the algorithm :

     Let, the original provided array is denoted as - A[ ] and a query as update( l, r, x). Where l is the left position index , r the right position index and x is the number by which the elements within the given range would be increased by.   

✔️So, what do we do is we make a new array - D[ i ] the difference array which will be updated according to this- D[ i ]= A[ i ] - A[ i-1 ] , which is simply storing the difference between two adjacent elements from the original array in the difference array .

✔️And when a update query is passed we just perform these simple changes in our difference arrays : 

   D[ l ]= D[ l ] + D[ x ]  &  D[ r+1 ]= D[ r+1 ] - x  

✔️These simple above changes make the updating time constant and we do this for as many queries that we get without losing a lot of time .

✔️Now, after we perform all our updates we have to now print the resultant array and we do that by following this :

The new a value of A[ i ] = A[ i-1 ] + D[ i ]  . 

The Code :

From the Classical Algorithm Reposititory. Do give a star ! ๐ŸŒŸ                     

So, that's how in constant time we can manage to update range queries . 

Thanks, Keep Learning ๐Ÿงก



linear search implementation understand search algorithms



Intro :

There a lot of sorting algorithms that exist today like - Binary Search, Linear  Search , Interpolation Search , Jump Search and many more .But the most basic one and the one search algorithm that most people learn when they learn to sort and search for the first time is Linear Search

In this blog we are going to learn the algorithm by understanding how it works ,it's implementation and it's time complexity .

Linear Search :

An algorithm which is used to find all the prime numbers in a given range .

Time Complexity : O(n)

 The Idea :

        So, the idea of the algorithm is simply that we find the required element by going through the whole range of given elements starting from one end to another.

Understanding the algorithm :

   Lets assume we are given a number a set of elements :{ 4 , 5 , 6 , 9 , 10 , 11 }. And we have to find 5 in the given range .So what we do is that we go through each of the element in the given range like - first 4 and we check is this equal to the our element ? So, as 4 is not  equal to 9 we do the same with the next numbers until the we stop which is when we reach 9 after going through 4 -> 5 -> 6 and 9.Thus we print that the element is found . And if we reach the end of the array and non of the element matches with our required element then we conclude that there is no such element in our range . 

The Code :


From the Classical Algorithm Reposititory. Do give a star ! ๐ŸŒŸ

Implementation :

✔️First we make an array which contains the given set of elements and store the element to be searched in a variable               

✔️We make a loop to traverse through the whole set and thus this step makes this an algorithm which runs on linear time i.e. O(n).

✔️In each iteration inside the loop we check whether the current element is equal to the element we are searching for .

✔️If it is equal at some point then we return 'true' that that it is found and thus getting out of the loop. Thus, making it obvious that if we traverse till the end of the loop and get out of the loop after the last iteration then we have not found the element and thus we return 'false'.                           

So, that's how in linear time we know that whether there is an element in the given array or not . 

Thanks, Keep Learning ๐Ÿงก



Sieve of Eratosthenes prime numbers linear time fast way thecsengineer

Intro :

So, as a programmer one of the first things that we learn is to check or  find the prime numbers. And the questions based on one algorithm comes up in different ways like : "Find the prime numbers between 2 to n integers" or "Find the nth prime number ". 

In this blog we are going to learn the algorithm which will never result in time limit exceeded as compared to a solution where we use the brute force or naieve algorithm .

This algorithm is known as Sieve of Eratosthenes .

Sieve Of Eratosthenes :

An algorithm which is used to find all the prime numbers in a given range .

Time Complexity : O(n log log n)

 The Idea :

        So, the idea of the algorithm is that a number is called a prime number only if no smaller prime numbers divide it .

Understanding the algorithm :

   Lets assume we are given a number a 5 and so what we do is first assume that all are prime numbers so we mark all of them 'true' in an array .Then we iterate through each one of it and and check if it is true then we mark all the numbers that is a multiple of the current number in the range starting from the number's square till the end of the given range .So, basically we are just marking out the numbers which are divisible by the smaller prime numbers and at last we are left with the numbers which got divided by no one so marked 'true' till the end . And of course we mark 1 and 0 as 'false' in the beginning as they are not prime and if considered would divide every other number in front of them and thus making them 'false' .

The Code :


From the Classical Algorithm Reposititory. Do give a star ! ๐ŸŒŸ

Implementation :

✔️First we make an array of size of the given range and initialize all  its value as 'true' assuming that all the numbers  are prime numbers.               

✔️Mark 0 and 1 as 'false' .

✔️Iterate through each of the number from 2 to n(last digit of the range).

✔️Check if the current number in the loop is marked 'true' not and whether it's square is less than n or the range as we have to traverse from the square of the current number to n marking 'false' all the multiples of the  current number .

✔️If it the check is passed we traverse from the square of the current  number till n and mark all of it's multiples 'false'.                            

So, at the end we are left with all those numbers which were not divisible by anyone marked 'true' or as we called those numbers as Prime Numbers in Earth. 

Thanks, Keep Learning ๐Ÿงก




The CS Engineer Programming coding goals future competitive programming


Hi,  I am Saumya Ranjan Nayak and this is my first blog post and thus the first step on this endless journey where at the end of the day I share  things that I learnt during the day and that may help you achieve your goals .

Intro :
    I am currently doing my bachelors in Computer Science in University in India and have a lot to achieve . I would be developing this habit of writing a blog post after dinner and before I go to bed. I had read about something called Habit Stacking in a book called Atomic Habits and it says that you can make a task a habit by associating it with an existing habit of yours and it totally makes sense .Its going to be pretty uncomfortable at first, but thats fine cause good things don't come easy .

         So, its the pandemic time going on and kind of 6th or 7th month of lockdown and I have been experimenting with me a lot and thus left a lot of things that seem to be illogical to be a part of the life and also taken up somethings and that align with my goals and though I am not good at those I am going to give everything to be good at it .
Well, I am pretty proud of me that I left social media and that's been great but I am on Twitter because first- it's the only social media where Elon is active and also I feel that people are more real on twitter and express who they really are as compared to Instagram. 
Just my perspective I might be wrong .

Believe :

So, honestly currently I am pretty much struggling very badly at competitive programming mainly I think because of my not so good background at math .But I know anything is possible with practice  and I believe in me and , its a thing I enjoy though its frustrating at times and I am trying to be more calm and thing as logically as possible. Currently its I guess the 5th or 6th month since I started doing competitive programming and till now I have almost solved minimum close to 250-300 problems from here and there .
Now I am solving the A2OJ ladders and I am at 71 out 100 problems of one of the ladders . 

I have decided to keep an habit of learning an algorithm the first thing in the morning and write a blog post or upload a video explaining it and practice problems during the day . 

Trying to visualize ideas :

    At night I will be working on Flutter projects of mine as I am learning it now and the right way to learn is to jump right in and start making something of your own . And it's pretty great as finally I found something that looks great without CSS and for some reason I don't know I hate CSS and also I am not into Web Dev . Not just telling naively, actually I had learnt HTML ,CSS and got attracted to React and in the lockdown and left it because there first I hated CSS and also no offence but I think a lot of people can make websites and I  just know that I don't want to do it . 

 But I always wanted to learn something by which I would be able to show my ideas visually and after some research I found Flutter and also Dart is mostly like C++ which is btw great and it just felt right and I jumped in . I am some app ideas in mind on which I would be working on soon .

Future Goals :

      I have planned how my future is going to look like and I will be working towards it . For example , I have planned to start my journey in Machine learning towards the end of my 2nd year and my goal always has been to be an AI engineer and to work and solve issues  that bring smile on the faces of people who are far far away from technology . Like the I like Google AI research team a lot and would love and will surely work there.

So , at last I just want to say that by  experimenting a lot I have narrowed down to these three things that I would be great at  :f
  • Problem Solving 
  • Competitive Programming
  • Machine Learning
  • Opensource
I guess that's  me . I hope you too achieve what you have as your goals .

Contact Me

Contact With Me