Leetcode: Continuous Subarray Sum

sphoorthi — Tue, 09 Jun 2020 04:56:40 +0000

Problem:

Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to a multiple of k, that is, sums up to n*k where n is also an integer.

Example 1:

Input: [23, 2, 4, 6, 7], k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:

Input: [23, 2, 6, 4, 7], k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

Constraints:

The length of the array won't exceed 10,000.
You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

Solution

The continuous sub array problems usually ask to find if there is a continuous sub array in array nums of a minimum length "l" which is multiple of a given target K

For any array nums with length n and the indices in order 0, i, j - where o < i < j < n [0, ...., i, ...., j, ... n-1]

Consider sumI = sum of elements from 0th index to ith index. (nums[0]+.....+nums[i]) and modI_K = remainder of sumI divided by K (i.e. modI_K = sumI % K)
Consider sumJ = sum of elements from 0th index to jth index. (nums[0]+.....+nums[j]) modJ_K = remainder of sumJ divided by K (i.e. modJ_K = sumJ % K)
By remainder theorem,
Given any integer A, and a positive integer B, there exist unique integers Q and R such that
A = B * Q + R where 0 ≤ R < B

To put it in mathematical terms,
Running sum from first element to index i (sumI) when divided by K, the modI_K and sumI can be writtern as
sumI = K * x + modI_K
Running sum from first element to index j (sumJ) when divided by K, the modJ_K and sumJ can be writtern as
sumJ = K * x + modJ_K

If mods of sumI and sumJ are equal modI_K == modJ_K it means that the difference between sumI and sumJ results in a constant multiplied by K.
sumI - sumJ = constant * K
That means there must exist a subarray sum that is a multiple of k.
So, to tackle these type of problems we need to save the remainders of running sum to help us identify that two running sums have a complimentary sum that is a multiple of K.

    public boolean checkSubarraySum(int[] nums, int k) {
        Map<Integer, Integer> remainderMap = new HashMap<>();

        remainderMap.put(0, -1);
        int runningSum = 0;
        int minLen = 2;

        for(int i = 0; i < nums.length; i++) {
            runningSum += nums[i];
            if(k != 0) {
                runningSum = runningSum % k;
            }
            if(remainderMap.containsKey(runningSum)) {
                if(i - remainderMap.get(runningSum) >= minLen)
                    return true;
            } else {
                remainderMap.put(runningSum, i);
            }
        }
        return false;
    }

Thank you for reading :)

What is Dependency Injection?

sphoorthi — Tue, 07 Apr 2020 18:20:33 +0000

Hello!!

Dependency Injection is not a new term for Devs with years of experience. But, for a junior developer it can be a confusing. This post aims to combine some examples I found on internet which were very useful for me in understanding and explain them in my words.

Let's see how wikipedia defines Dependency Injection:

In software engineering, dependency injection is a technique whereby one object supplies the dependencies of another object. A "dependency" is an object that can be used, for example as a service. Instead of a client specifying which service it will use, something tells the client what service to use.

Well, it perfectly states what dependency injection is.

Now, let me try explaining it by comparing with a real life scenario,

Consider that your work requires you to travel many times a month and your organization has preferred set of agencies to be contacted to for the travel.

The travel planning can be imagined in two scenarios,

Scenario 1
You have the complete details of the preferred airline, rental car or cab agencies to be contacted. So,

You call the preferred agencies for the flight and car bookings.
You give them the destination and date of travel.
They make the necessary bookings and give you the itinerary.

Scenario 2
There is a travel administration department which handles the travel for the employees.It provides online chat services or automated telephonic services which lets you connect with these agencies.

Whenever you need to travel, you use one of those services and give them your travel details like destination, date and any preferences specific to you. The agencies do the necessary bookings and hands you the travel itinerary.

Let us suppose that your organization changes the preferred agencies and the new agencies have new contact details and completely different booking mechanisms. Then,

In scenario 1, you need to update all the contacts and the adapt to the new booking mechanisms of the new agencies.

In scenario 2, the travel administration department would readjust its workflow behind the scenes to be able to communicate with the agencies so as to not impact you.

Ok, How does this relate to dependency injection?
In both the scenarios, you are the client and you are dependent upon the services provided by the agencies.

However Scenario 2 has a few differences, the administrative department is giving you the services of the agencies as dependencies in a way that you can reuse them. If there is any change in the services there need not be
any change from you as a client.

Dependency Injection in a software application context:

Any application can be pictured as a graph of objects which are dependent on each other.
Each object plays either the role of client and uses other objects (services) or offers services to another component or both.

Each object needs to know “which” objects to communicate with, “where” to locate them, and “how” to communicate with them. When the way such services/objects can be accessed is changed they can potentially lead to a lot changes on the client side.

Transferring the task of creating the object to someone else and directly using the dependency is called dependency injection.

Creating and maintaining these objects is usually done by external containers which are also responsible of injecting the dependencies into the objects. These containers are often provided by the frameworks supporting different programming languages.

For the Dependency Injection to be achieved we need,

A Service which provides services.
A client that want to use these services.
An Interface, which is the abstraction between service and client.
An injector/containers which creates a service instance and injects it into the client.

The organization example in this article is inspired from A beginners guide to Dependency Injection

DEV Community: sphoorthi

Leetcode: Continuous Subarray Sum

Problem:

Solution

What is Dependency Injection?