Sum of All Odd Length Subarrays

Sum of All Odd Length Subarrays:

Problem Description:

Given an array of positive integers arr, calculate the sum of all possible odd-length subarrays.

A subarray is a contiguous subsequence of the array.

Return the sum of all odd-length subarrays of arr.


Example 1:

Input: arr = [1,4,2,5,3]

Output: 58

Explanation: The odd-length subarrays of arr and their sums are:

[1] = 1

[4] = 4

[2] = 2

[5] = 5

[3] = 3

[1,4,2] = 7

[4,2,5] = 11

[2,5,3] = 10

[1,4,2,5,3] = 15

If we add all these together we get 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58


Example 2:

Input: arr = [1,2]

Output: 3

Explanation: There are only 2 subarrays of odd length, [1] and [2]. Their sum is 3.


Example 3:

Input: arr = [10,11,12]

Output: 66

 

Constraints:

1 <= arr.length <= 100

1 <= arr[i] <= 1000


Solution:

Optimized Solution:


class Solution {

    public int sumOddLengthSubarrays(int[] arr) {

        int n = arr.length, res = 0, start = 0, end = 0,elementappearsinhowmanysubarrays = 0,elementappearinoddsubarrays=0  ;

        for(int i=0; i<arr.length; i++)

        {

             start = n-i;

             end = i+1;

             elementappearsinhowmanysubarrays = start * end;

             elementappearinoddsubarrays = elementappearsinhowmanysubarrays/2;

            if(elementappearsinhowmanysubarrays%2 == 1)

            {

                elementappearinoddsubarrays += 1;

            }

            res = res + elementappearinoddsubarrays*arr[i];

        }

        return res;

    }

}


Time Complexity☝ O(n)


Brute Force Solution:


class Solution {

    public int sumOddLengthSubarrays(int[] arr) {

        int repeat = 0;

        repeat = (arr.length% 2 == 0) ? arr.length-1:arr.length;

        int c = 1, sm = 0;  //c values are 1, 3, 5

        while(c<=repeat)

        {

            for(int i=0; i<=arr.length-c ; i++)

            {

                for(int j=i; j<i+c; j++)

                {

                    sm+=arr[j];

                }

            }

            c+=2;

        }

        return sm;

    }

}


Execution:

Successfully Executed




Reference☝ Sum of All Odd Length Subarrays in Java


                                                                    Happy Coding 💻:-)

Comments

Post a Comment

Popular posts from this blog

Valid Username Regular Expression

Valid Username Regular Expression: Problem Description: You are updating the username policy on your company's internal networking platform. According to the policy, a username is considered valid if all the following constraints are satisfied: The username consists of 8 to 30 characters inclusive. If the username consists of less than  or greater than 8 characters, then it is an invalid username. The username can only contain alphanumeric characters and underscores (_). Alphanumeric characters describe the character set consisting of lowercase characters[a-z] , uppercase characters[A-Z] , and digits[0-9]. The first character of the username must be an alphabetic character, i.e., either lowercase character [a-z] or uppercase character [A-Z]. Update the value of regularExpression field in the UsernameValidator class so that the regular expression only matches with valid usernames. Input Format The first line of input contains an integer , describing the total number of usernames. Ea...
Read more

Rotate String in Right Direction in java

Rotate String in Right Direction in java: Program: import java.util.*; public class RotateString { public static void main(String[] args) { Scanner s = new Scanner(System.in); int n = s.nextInt(); char[] ch = new char[n]; for(int i=0;i<n;i++) { ch[i] = s.next().charAt(0); } int r = s.nextInt(); char temp = 'a'; r=r%n; while(r>0) { temp = ch[n-1]; for(int i = n-1; i>0;i--) { ch[i] = ch[i-1]; } ch[0] = temp; System.out.println("r: " + r); for(int i=0;i<n;i++) { System.out.print(ch[i]); } System.out.println(); r--; } for(int i=0;i<n;i++) { System.out.print(ch[i]); } } } Output : 5 a s d f g 3 r: 3 gasdf r: 2 fgasd r: 1 dfgas dfgas                                                            Happy Coding 💻:-)
Read more

Sum of Elements of Lower Triangular Matrix

Sum of Elements of Lower Triangular Matrix: Program: import java.util.Scanner; public class LowerTriangularElementsSum { public static void main(String[] args) { int r, c; Scanner s = new Scanner(System.in); r = s.nextInt(); c = s.nextInt(); if(r!=c) { System.exit(0); } int[][] matrix = new int[r][c]; for(int i = 0; i<r; i++) { for(int j = 0; j<c;j++) { matrix[i][j] = s.nextInt(); } } int sum = 0; for(int i = 0; i<r; i++) { for(int j = 0;j<c; j++) { if(i>=j) { System.out.print(matrix[i][j]); System.out.print(" "); sum+=matrix[i][j]; } } } System.out.println("\nThe sum of Lower triangular elements of a matrix is: " + sum); } } /* In other words, a square matrix is lower triangular if all its entries above the main diagonal are zero.  * Example of a 3 × 3 lower triangular matrix: Diagonal matrices are both upper  *and lower triangular since they have zeroes a...
Read more