If people are doubting how far you can go, go so far that you can't hear them anymore.
~Michele Ruiz
Arithmetic Slices - 1
Welcome Back Reader!
In this article we will discuss about the first problem based on "Dynamic Programming" i.e.
"Arithmetic Slices - 1".
Before you move any further, it is advised that you give this problem a fair try.
Let's jump to the problem.
In this problem you are given an array(arr) of integers.
All you are required to do is to find the count of arithmetic slices in the given array.
Arithmetic slice is defined as the subarray having all its elements in A.P and the length of the
subarray should be greater than or equal to 3.
For example:
Sample Input:
4
1 2 3 4
Sample Output:3
How?
Three arithmetic slices in the given array are {1, 2, 3}, {1, 2, 3, 4}, and {2, 3, 4}.
For more clarity of the question, watch part of the video.
Approach:
Moving On:
To solve this problem, first of all we need a 1D dp array, of size n (equal to input arrays
length) and then start filling it from the left.
This dp array at any index I will store the number of A.P.(s) ending at index I in the input array of length greater than or equal to 3.
That means dp will store 0 at index 0 and 1 as the length of A.P. (if possible) will be 1 and 2.
From index 2 onwards while filling the dp array (when length can actually be at least of length 3), we check that the difference of values present at index I and i-1 equals to the difference of values present at index i-1 and i-2 in the input array.
And if yes, then we will increment the value present at dp[i-1] by 1 and place it at dp[i].
For the final answer, we need to calculate the sum of values stored in the dp array which will basically give the count of A.P.(s) in the given array.
For example, consider the array arr, {2, 5, 9, 12, 15, 18, 22, 26, 34, 36, 38, 40, 41}.
At index 0 and 1, simply store 0 as there is no A.P. possible of length 3.
At index 2, check whether arr[2]- arr [1] equals arr [1]- arr [0]. No they are not, so place a 0 at dp[2].
Next check the same for index 3, whether arr [3]- arr [2] equals arr [2]- arr [1]. Since they are not so, place a 0 at dp[3].
Similarly for index 4, check whether arr [4]- arr [3] equals arr [3]- arr [2]. As in this case they are equal to place a value at dp[4] which is present at dp[3] by incrementing it by 1 .
Similarly for index 5, check whether arr [5]- arr [4] equals arr [4]- arr [3]. As they are equal to place a value at dp[5] which is present at dp[4] by incrementing it by 1 .
Similarly fill the rest of the dp array.
And at last, the sum of the dp array will be the final answer.
For more clarity of this part; watch part of the video.
Let's try to code this!
//1 - First of all, define a variable answer ans to 0.
//2 - Then create a dp array of length same as input array's length.
//3 - After that, apply a for loop on the dp array's length to fill the dp array.
//4 -Then use the if condition to check if arr[i]-arr[i-1] equals to arr[i-1]-arr[i-2].
//5 - If the condition is true then increment the value present at dp[i-1] and place it in dp[i].
//6 -Simultaneously, keep updating the variable ans by adding the dp[i] to the previous ans which will store the total of dp array (count of possible A.P.(s)) by the end of loop.
//7 - At last return the ans.
For more clarity of the code, watch part of the video.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] arr = new int[n];
for(int i = 0 ; i < n; i++){
arr[i] = scn.nextInt();
}
System.out.println(solution(arr));
}
public static int solution(int[] A) {
int ans=0;
// to store the count of slices including the element i in the last
int[] dp=new int[A.length];
for (int i = 2; i < A.length; i++) {
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
// new count will be 1 more due to A[i-2],A[i-1],A[i]
dp[i]=dp[i-1]+1;
ans+=dp[i];
}
}
return ans;
}
}
java;
true";
Analysis
Recursion approach:
A for loop is used on input array' length which makes the time complexity of order O(n).
Space Complexity: O(n)
One n sized 1D array is used which makes the space complexity of O(n).
We hope that this article was helpful. If somehow you are finding it difficult to understand this problem then we advise you to watch our video lecture of this problem.
Trust me it will just get easier to understand after you have watched the solution video.
You can contact us via our website. Doubts, suggestions and feedback are always welcomed.
It is also advised that you follow the sequence of modules and questions which is there on our website.
Keep practicing more and more problems daily. Meditate enough on each step of each problem.
All the best for an exciting future!
Happy Coding!
