Print all subarrays with 0 sum

Last Updated : 28 Jun, 2024

Recommended Problem

Zero Sum Subarrays

Companies:

Amazon Microsoft

+1 more

Show Topics

Topics:

+1 more

Solve Problem

Medium

51.49%

1.3L

Given an array arr[] of size n, the task is to print all subarrays in the array which has sum 0.

Examples:

Input: arr = [6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7]
Output:

Subarray found from Index 2 to 4
Subarray found from Index 2 to 6
Subarray found from Index 5 to 6
Subarray found from Index 6 to 9
Subarray found from Index 0 to 10
Input: arr = [1, 2, -3, 3, -1, -1]
Output:

Subarray found from Index 0 to 2
Subarray found from Index 2 to 3
Subarray found from Index 3 to 5

Approaches to print all subarrays with 0 sum:

Table of Content

Approaches to print all subarrays with 0 sum:

[Naive Approach] By generating all possible subarrays – O(n²) time and O(1) auxiliary space

The very basic approach is to considers all possible subarrays and checks if their sum is zero. Although this approach is simple but inefficient also for large arrays.

Code Implementation:

C++

// C++ program to print all subarrays
// in the array which has sum 0
#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int> > findSubArrays(int arr[], int n)
{

    // Array to store all the start and end
    // indices of subarrays with 0 sum
    vector<pair<int, int> > output;
    for (int i = 0; i < n; i++) {
        int prefix = 0;
        for (int j = i; j < n; j++) {
            prefix += arr[j];
            if (prefix == 0)
                output.push_back({ i, j });
        }
    }

    return output;
}

// Function to print all subarrays with 0 sum
void print(vector<pair<int, int> > output)
{
    for (auto it = output.begin(); it != output.end(); it++)
        cout << "Subarray found from Index " << it->first
             << " to " << it->second << endl;
}

// Driver code
int main()
{

    // Given array
    int arr[] = { 6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7 };
    int n = sizeof(arr) / sizeof(arr[0]);

    // Function Call
    vector<pair<int, int> > output = findSubArrays(arr, n);

    // if we didn’t find any subarray with 0 sum,
    // then subarray doesn’t exists
    if (output.size() == 0) {
        cout << "No subarray exists";
    }
    else {
        print(output);
    }
    return 0;
}

Java

// Java program to print all subarrays
// in the array which has sum 0
import java.io.*;
import java.util.*;

// User defined pair class
class Pair {
    int first, second;
    Pair(int a, int b)
    {
        first = a;
        second = b;
    }
}

public class GFG {
    static ArrayList<Pair> findSubArrays(int[] arr, int n)
    {
        // Array to store all the start and end
        // indices of subarrays with 0 sum
        ArrayList<Pair> out = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int prefix = 0;
            for (int j = i; j < n; j++) {
                prefix += arr[j];
                if (prefix == 0)
                    out.add(new Pair(i, j));
            }
        }
        return out;
    }

    // Function to print all subarrays with 0 sum
    static void print(ArrayList<Pair> out)
    {
        for (int i = 0; i < out.size(); i++) {
            Pair p = out.get(i);
            System.out.println("Subarray found from Index "
                               + p.first + " to "
                               + p.second);
        }
    }

    // Driver code
    public static void main(String args[])
    {

        // Given array
        int[] arr
            = { 6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7 };
        int n = arr.length;

        // Function Call
        ArrayList<Pair> out = findSubArrays(arr, n);

        // if we didn’t find any subarray with 0 sum,
        // then subarray doesn’t exists
        if (out.size() == 0)
            System.out.println("No subarray exists");
        else
            print(out);
    }
}

Python

# User defined pair class
class Pair:
    first = 0
    second = 0

    def __init__(self, a,  b):
        self.first = a
        self.second = b


class GFG:
    @staticmethod
    def findSubArrays(arr,  n):

        # Array to store all the start and end
        # indices of subarrays with 0 sum
        out = []
        i = 0
        while (i < n):
            prefix = 0
            j = i
            while (j < n):
                prefix += arr[j]
                if (prefix == 0):
                    out.append(Pair(i, j))
                j += 1
            i += 1
        return out

    # Function to print all subarrays with 0 sum
    @staticmethod
    def print(out):
        i = 0
        while (i < len(out)):
            p = out[i]
            print("Subarray found from Index " +
                  str(p.first) + " to " + str(p.second))
            i += 1

    # Driver code
    @staticmethod
    def main(args):

        # Given array
        arr = [6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7]
        n = len(arr)

        # Function Call
        out = GFG.findSubArrays(arr, n)

        # if we didn't find any subarray with 0 sum,
        # then subarray doesn't exists
        if (len(out) == 0):
            print("No subarray exists")
        else:
            GFG.print(out)


if __name__ == "__main__":
    GFG.main([])

C#

using System;
using System.Collections.Generic;

class GFG
{
  
  // Array to store all the start and end
  // indices of subarrays with 0 sum
  static List<Tuple<int, int>> findSubArrays(int[] arr, int n)
  {
    var output = new List<Tuple<int, int>>();
    for (int i = 0; i < n; i++)
    {
      int prefix = 0;
      for (int j = i; j < n; j++)
      {
        prefix += arr[j];
        if (prefix == 0)
          output.Add(Tuple.Create(i, j));
      }
    }

    return output;
  }

  // Function to print all subarrays with 0 sum
  static void print(List<Tuple<int, int>> output)
  {
    foreach (var subArray in output)
      Console.Write("Subarray found from Index " + subArray.Item1 + " to " + subArray.Item2+"\n");
  }

  // Driver code
  public static void Main()
  {
    // Given array
    int[] arr = { 6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7 };
    int n = arr.Length;

    // Function Call
    List<Tuple<int, int>> output = findSubArrays(arr, n);

    // if we didn’t find any subarray with 0 sum,
    // then subarray doesn’t exists
    if (output.Count == 0)
    {
      Console.WriteLine("No subarray exists");
    }
    else
    {
      print(output);
    }
  }
}

JavaScript

// Javascript program to print all subarrays
// in the array which has sum 0
function findSubArrays(arr, n)
{

    // Array to store all the start and end
    // indices of subarrays with 0 sum
    let out =[];
    for (let i = 0; i < n; i++) {
        let prefix = 0;
        for (let j = i; j < n; j++) {
            prefix += arr[j];
            if (prefix == 0)
                out.push([i, j]);
        }
    }

    return out;
}

// Function to print all subarrays with 0 sum
function print(out)
{
    for (let it of out)
        console.log("Subarray found from Index " + it[0]
             + " to " + it[1]);
}

// Driver code
// Given array
let arr = [ 6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7 ];
let n = arr.length ;

// Function Call
let out = findSubArrays(arr, n);

// if we didn’t find any subarray with 0 sum,
// then subarray doesn’t exists
if (out.length == 0) {
    console.log("No subarray exists");
}
else {
    print(out);
}

Output

Subarray found from Index 0 to 10
Subarray found from Index 2 to 4
Subarray found from Index 2 to 6
Subarray found from Index 5 to 6
Subarray found from Index 6 to 9

Time Complexity: O(N²) since we are using 2 loops.
Auxiliary Space: O(1), as constant extra space is required.

[Expected Approach] Using Hashing – O(n) time and O(n) auxiliary space

A more efficient approach is to use hashing to store the cumulative sum of elements and their indices. This allows for checking if a subarray with zero sum exists in constant time.

Below is detailed Steps of intuition:

Create a hash map to store the cumulative sum and corresponding indices.
Initialize the cumulative sum to zero.
Traverse the array:
Add the current element to the cumulative sum.
If the cumulative sum is zero, a subarray from the beginning to the current index is found.
If the cumulative sum is already present in the hash map, it means there is a subarray with zero sum.
Store the cumulative sum and index in the hash map.

Code Implementation

C++

// C++ program to print all subarrays
// in the array which has sum 0
#include <bits/stdc++.h>
using namespace std;

// Function to print all subarrays in the array which
// has sum 0
vector<pair<int, int> > findSubArrays(int arr[], int n)
{
    // create an empty map
    unordered_map<int, vector<int> > map;

    // create an empty vector of pairs to store
    // subarray starting and ending index
    vector<pair<int, int> > out;

    // Maintains sum of elements so far
    int sum = 0;

    for (int i = 0; i < n; i++) {
        // add current element to sum
        sum += arr[i];

        // if sum is 0, we found a subarray starting
        // from index 0 and ending at index i
        if (sum == 0)
            out.push_back(make_pair(0, i));

        // If sum already exists in the map there exists
        // at-least one subarray ending at index i with
        // 0 sum
        if (map.find(sum) != map.end()) {
            // map[sum] stores starting index of all
            // subarrays
            vector<int> vc = map[sum];
            for (auto it = vc.begin(); it != vc.end(); it++)
                out.push_back(make_pair(*it + 1, i));
        }

        // Important - no else
        map[sum].push_back(i);
    }

    // return output vector
    return out;
}

// Utility function to print all subarrays with sum 0
void print(vector<pair<int, int> > out)
{
    for (auto it = out.begin(); it != out.end(); it++)
        cout << "Subarray found from Index " << it->first
             << " to " << it->second << endl;
}

// Driver code
int main()
{
    int arr[] = { 6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7 };
    int n = sizeof(arr) / sizeof(arr[0]);

    vector<pair<int, int> > out = findSubArrays(arr, n);

    // if we didn’t find any subarray with 0 sum,
    // then subarray doesn’t exists
    if (out.size() == 0)
        cout << "No subarray exists";
    else
        print(out);

    return 0;
}

Java

// Java program to print all subarrays
// in the array which has sum 0
import java.io.*;
import java.util.*;

// User defined pair class
class Pair {
    int first, second;
    Pair(int a, int b)
    {
        first = a;
        second = b;
    }
}

public class GFG {
    // Function to print all subarrays in the array which
    // has sum 0
    static ArrayList<Pair> findSubArrays(int[] arr, int n)
    {
        // create an empty map
        HashMap<Integer, ArrayList<Integer> > map
            = new HashMap<>();

        // create an empty vector of pairs to store
        // subarray starting and ending index
        ArrayList<Pair> out = new ArrayList<>();

        // Maintains sum of elements so far
        int sum = 0;

        for (int i = 0; i < n; i++) {
            // add current element to sum
            sum += arr[i];

            // if sum is 0, we found a subarray starting
            // from index 0 and ending at index i
            if (sum == 0)
                out.add(new Pair(0, i));
            ArrayList<Integer> al = new ArrayList<>();

            // If sum already exists in the map there exists
            // at-least one subarray ending at index i with
            // 0 sum
            if (map.containsKey(sum)) {
                // map[sum] stores starting index of all
                // subarrays
                al = map.get(sum);
                for (int it = 0; it < al.size(); it++) {
                    out.add(new Pair(al.get(it) + 1, i));
                }
            }
            al.add(i);
            map.put(sum, al);
        }
        return out;
    }

    // Utility function to print all subarrays with sum 0
    static void print(ArrayList<Pair> out)
    {
        for (int i = 0; i < out.size(); i++) {
            Pair p = out.get(i);
            System.out.println("Subarray found from Index "
                               + p.first + " to "
                               + p.second);
        }
    }

    // Driver code
    public static void main(String args[])
    {
        int[] arr
            = { 6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7 };
        int n = arr.length;

        ArrayList<Pair> out = findSubArrays(arr, n);

        // if we did not find any subarray with 0 sum,
        // then subarray does not exists
        if (out.size() == 0)
            System.out.println("No subarray exists");
        else
            print(out);
    }
}

Python

# Python3 program to print all subarrays
# in the array which has sum 0

# Function to get all subarrays
# in the array which has sum 0


def findSubArrays(arr, n):

    # create a python dict
    hashMap = {}

    # create a python list
    # equivalent to ArrayList
    out = []

    # tracker for sum of elements
    sum1 = 0
    for i in range(n):

        # increment sum by element of array
        sum1 += arr[i]

        # if sum is 0, we found a subarray starting
        # from index 0 and ending at index i
        if sum1 == 0:
            out.append((0, i))
        al = []

        # If sum already exists in the map
        # there exists at-least one subarray
        # ending at index i with 0 sum
        if sum1 in hashMap:

            # map[sum] stores starting index
            # of all subarrays
            al = hashMap.get(sum1)
            for it in range(len(al)):
                out.append((al[it] + 1, i))
        al.append(i)
        hashMap[sum1] = al
    return out

# Utility function to print
# all subarrays with sum 0


def printOutput(output):
    for i in output:
        print("Subarray found from Index " +
              str(i[0]) + " to " + str(i[1]))


# Driver Code
if __name__ == '__main__':
    arr = [6, 3, -1, -3, 4, -2,
           2, 4, 6, -12, -7]
    n = len(arr)
    out = findSubArrays(arr, n)

    # if we did not find any subarray with 0 sum,
    # then subarray does not exists
    if (len(out) == 0):
        print("No subarray exists")
    else:
        printOutput(out)

C#

// C# program to print all subarrays
// in the array which has sum 0
using System;
using System.Collections.Generic;

// User defined pair class
class Pair {
    public int first, second;
    public Pair(int a, int b)
    {
        first = a;
        second = b;
    }
}

class GFG {
    // Function to print all subarrays
    // in the array which has sum 0
    static List<Pair> findSubArrays(int[] arr, int n)
    {
        // create an empty map
        Dictionary<int, List<int> > map
            = new Dictionary<int, List<int> >();

        // create an empty vector of pairs to store
        // subarray starting and ending index
        List<Pair> outt = new List<Pair>();

        // Maintains sum of elements so far
        int sum = 0;

        for (int i = 0; i < n; i++) {
            // add current element to sum
            sum += arr[i];

            // if sum is 0, we found a subarray starting
            // from index 0 and ending at index i
            if (sum == 0)
                outt.Add(new Pair(0, i));
            List<int> al = new List<int>();

            // If sum already exists in the map there exists
            // at-least one subarray ending at index i with
            // 0 sum
            if (map.ContainsKey(sum)) {
                // map[sum] stores starting index
                // of all subarrays
                al = map[sum];
                for (int it = 0; it < al.Count; it++) {
                    outt.Add(new Pair(al[it] + 1, i));
                }
            }
            al.Add(i);
            if (map.ContainsKey(sum))
                map[sum] = al;
            else
                map.Add(sum, al);
        }
        return outt;
    }

    // Utility function to print all subarrays with sum 0
    static void print(List<Pair> outt)
    {
        for (int i = 0; i < outt.Count; i++) {
            Pair p = outt[i];
            Console.WriteLine("Subarray found from Index "
                              + p.first + " to "
                              + p.second);
        }
    }

    // Driver code
    public static void Main(String[] args)
    {
        int[] arr
            = { 6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7 };
        int n = arr.Length;

        List<Pair> outt = findSubArrays(arr, n);

        // if we did not find any subarray with 0 sum,
        // then subarray does not exists
        if (outt.Count == 0)
            Console.WriteLine("No subarray exists");
        else
            print(outt);
    }
}

JavaScript

// JavaScript program to print all subarrays
// in the array which has sum 0

// Function to print all subarrays in the array which
// has sum 0
function findSubArrays(arr, n)
{
    // create an empty map
    let map = {};
 
    // create an empty vector of pairs to store
    // subarray starting and ending index
    let out = [];
 
    // Maintains sum of elements so far
    let sum = 0;
 
    for (var i = 0; i < n; i++)
    {
        // add current element to sum
        sum += arr[i];
 
        // if sum is 0, we found a subarray starting
        // from index 0 and ending at index i
        if (sum == 0)
            out.push([0, i]);
 
        // If sum already exists in the map there exists
        // at-least one subarray ending at index i with
        // 0 sum
        if (map.hasOwnProperty(sum))
        {
            // map[sum] stores starting index of all subarrays
            let vc = map[sum];
            for (let it of vc)
                out.push([it + 1, i]);
        }
        else
            map[sum] = [];
 
        // Important - no else
        map[sum].push(i);
    }
 
    // return output vector
    return out;
}
 
// Utility function to print all subarrays with sum 0
function print(out)
{
    for (let it of out)
        console.log("Subarray found from Index " + it[0] + " to " + it[1]);
}
 
 
// Driver code
let arr = [6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7];
let n = arr.length;
 
let out = findSubArrays(arr, n);
 
// if we didn’t find any subarray with 0 sum,
// then subarray doesn’t exists
if (out.length == 0)
    console.log("No subarray exists");
else
    print(out);

Output

Subarray found from Index 2 to 4
Subarray found from Index 2 to 6
Subarray found from Index 5 to 6
Subarray found from Index 6 to 9
Subarray found from Index 0 to 10

Time Complexity: O(n), where n is the number of elements in the array.
Auxiliary Space: O(n), for storing the hash map.

A

Aditya Goel

News

Improve

Print subarray with maximum sum

Similar Reads

Split array into K subarrays such that sum of maximum of all subarrays is maximized

Given an array arr[] of size N and a number K, the task is to partition the given array into K contiguous subarrays such that the sum of the maximum of each subarray is the maximum possible. If it is possible to split the array in such a manner, then print the maximum possible sum. Otherwise, print "-1". Examples: Input: arr[] = {5, 3, 2, 7, 6, 4},

Split into K subarrays to minimize the maximum sum of all subarrays

Given an Array[] of N elements and a number K. ( 1 <= K <= N ) . Split the given array into K subarrays (they must cover all the elements). The maximum subarray sum achievable out of K subarrays formed, must be the minimum possible. Find that possible subarray sum.Examples: Input : Array[] = {1, 2, 3, 4}, K = 3 Output : 4 Optimal Split is {1,

Split given arrays into subarrays to maximize the sum of maximum and minimum in each subarrays

Given an array arr[] consisting of N integers, the task is to maximize the sum of the difference of the maximum and minimum in each subarrays by splitting the given array into non-overlapping subarrays. Examples: Input: arr[] = {8, 1, 7, 9, 2}Output: 14Explanation:Split the given array arr[] as {8, 1}, {7, 9, 2}. Now, the sum of the difference maxi

Print all subarrays with sum in a given range

Given an array arr[] of positive integers and two integers L and R defining the range [L, R]. The task is to print the subarrays having sum in the range L to R. Examples: Input: arr[] = {1, 4, 6}, L = 3, R = 8Output: {1, 4}, {4}, {6}.Explanation: All the possible subarrays are the following{1] with sum 1. {1, 4} with sum 5. {1, 4, 6} with sum 11.{4

Differences between number of increasing subarrays and decreasing subarrays in k sized windows

Given an array of integers and k, find the difference between the number of the strictly increasing number of subarrays (of size more than one) and the number of the strictly decreasing subarray in the window of size k. Examples: Input : nums = {10, 20, 30, 15, 15}; k = 3; Output : 3, 0, -1 Explanation For the first window of [10, 20, 30], there ar

Split given Array in minimum number of subarrays such that rearranging the order of subarrays sorts the array

Given an array arr[] consisting of N integers, the task is to find the minimum number of splitting of array elements into subarrays such that rearranging the order of subarrays sorts the given array. Examples: Input: arr[] = {6, 3, 4, 2, 1}Output: 4Explanation:The given array can be divided into 4 subarrays as {6}, {3, 4}, {2}, {1} and these subarr

Check if Array can be split into subarrays such that XOR of length of Longest Decreasing Subsequences of those subarrays is 0

Given an array of integers arr[] of size N, the task is to check whether arr[] can be split into different subarrays such that on taking the XOR of lengths of LDS (Longest decreasing subsequences) of all the subarrays is equal to 0. Print 'YES' if it is possible to split else print 'NO'. Examples: Input: arr[] = {1, 0, 3, 4, 5}Output: YESExplanatio

Print indices of pair of array elements required to be removed to split array into 3 equal sum subarrays

Given an array arr[] consisting of N integers, the task is to print the indices of two array elements required to be removed such that the given array can be split into three subarrays of equal sum. If not possible to do so, then print "-1". Examples: Input: arr[] = {2, 5, 12, 7, 19, 4, 3}Output: 2 4Explanation:Removing arr[2] and arr[4] modifies a

For all Array elements find Product of Sum of all smaller and Sum of all greater elements

Given an array arr[] of integers of length N, the task is to find the product of the sum of all the numbers larger than that number with the sum of all the numbers less than that number for each number in the array. Examples: Input: arr[] = {8, 4, 9, 3}, N = 4Output:- 63, 51, 0, 0Explanation:For first number 8: Sum of elements smaller than this is

Count all subarrays whose sum can be split as difference of squares of two Integers

Given an array arr[], the task is to count all subarrays whose sum can be split as the difference of the squares of two integers. Examples: Input: arr[] = {1, 3, 5} Output: 6 Explanation: There are six subarrays which can be formed from the array whose sum can be split as the difference of squares of two integers. They are: Sum of the subarray {1}

Generate Array whose sum of all K-size subarrays divided by N leaves remainder X

Given three integer N, K and X, the task is to create an array of length N such that sum of all its K-length subarrays modulo N is X.Examples: Input: N = 6, K = 3, X = 3 Output: 9 6 6 9 6 6 Explanation: All subarrays of length 3 and their respective sum%N values are as follows: [9, 6, 6] Sum = 21 % 6 = 3 [6, 6, 9] sum = 21 % 6 = 3 [6, 9, 6] sum = 2

Sum of bitwise OR of all subarrays

Given an array of positive integers, find the total sum after performing the bit wise OR operation on all the sub arrays of a given array. Examples: Input : 1 2 3 4 5 Output : 71 Input : 6 5 4 3 2 Output : 84 First initialize the two variable sum=0, sum1=0, variable sum will store the total sum and, with sum1 we will perform bitwise OR operation fo

Sum of XOR of all subarrays

Given an array containing N positive integers, the task is to find the sum of XOR of all sub-arrays of the array. Examples: Input : arr[] = {1, 3, 7, 9, 8, 7} Output : 128 Input : arr[] = {3, 8, 13} Output : 46 Explanation for second test-case: XOR of {3} = 3 XOR of {3, 8} = 11 XOR of {3, 8, 13} = 6 XOR of {8} = 8 XOR of {8, 13} = 5 XOR of {13} = 1

Sum of bitwise AND of all subarrays

Given an array consisting of N positive integers, find the sum of bit-wise and of all possible sub-arrays of the array. Examples: Input : arr[] = {1, 5, 8} Output : 15 Bit-wise AND of {1} = 1 Bit-wise AND of {1, 5} = 1 Bit-wise AND of {1, 5, 8} = 0 Bit-wise AND of {5} = 5 Bit-wise AND of {5, 8} = 0 Bit-wise AND of {8} = 8 Sum = 1 + 1 + 0 + 5 + 0 +

Sum of minimum element of all subarrays of a sorted array

Given a sorted array A of n integers. The task is to find the sum of the minimum of all possible subarrays of A. Examples: Input: A = [ 1, 2, 4, 5] Output: 23 Subsequences are [1], [2], [4], [5], [1, 2], [2, 4], [4, 5] [1, 2, 4], [2, 4, 5], [1, 2, 4, 5] Minimums are 1, 2, 4, 5, 1, 2, 4, 1, 2, 1. Sum is 23Input: A = [1, 2, 3] Output: 10 Approach: Th

Sum of maximum of all subarrays | Divide and Conquer

Given an array arr[] of length N, the task is to find the sum of the maximum elements of every possible sub-array of the array.Examples: Input : arr[] = {1, 3, 1, 7} Output : 42 Max of all sub-arrays: {1} - 1 {1, 3} - 3 {1, 3, 1} - 3 {1, 3, 1, 7} - 7 {3} - 3 {3, 1} - 3 {3, 1, 7} - 7 {1} - 1 {1, 7} - 7 {7} - 7 1 + 3 + 3 + 7 + 3 + 3 + 7 + 1 + 7 + 7 =

Find all subarrays with sum in the given range

Given an unsorted array of size, N. Find subarrays that add to a sum in the given range L-R. Examples: Input: arr[] = {2, 3, 5, 8}, L = 4, R = 13Output: The indexes of subarrays are {0, 1}, {0, 2}, {1, 2}, {2, 2}, {2, 3}, {3, 3} Input: arr[] = {1, 4, 6}, L = 3, R = 8Output: The indexes of subarrays are {0, 1}, {1, 1}, {2, 2} Naive approach: Follow

Calculate the Sum of GCD over all subarrays

Given an array of integers, the task is to calculate the sum of GCD of all the subarrays of an array. GCD of an array is defined as the GCD of all the elements present in it. More formally, [Tex]GCD(A[n]) = GCD(A_1, A_2, A_3....A_n) [/Tex]. Summation of all the GCDs can be defined as [Tex]\sum_{i=1}^{n}\sum_{j=i}^{n} GCD(A_{ij}) [/Tex]where [Tex]A_

Maximum length L such that the sum of all subarrays of length L is less than K

Given an array of length N and an integer K. The task is to find the maximum length L such that all the subarrays of length L have sum of its elements less than K.Examples: Input: arr[] = {1, 2, 3, 4, 5}, K = 20 Output: 5 The only subarray of length 5 is the complete array and (1 + 2 + 3 + 4 + 5) = 15 < 20. Input: arr[] = {1, 2, 3, 4, 5}, K = 10

Sum of all subarrays of size K

Given an array arr[] and an integer K, the task is to calculate the sum of all subarrays of size K. Examples: Input: arr[] = {1, 2, 3, 4, 5, 6}, K = 3 Output: 6 9 12 15 Explanation: All subarrays of size k and their sum: Subarray 1: {1, 2, 3} = 1 + 2 + 3 = 6 Subarray 2: {2, 3, 4} = 2 + 3 + 4 = 9 Subarray 3: {3, 4, 5} = 3 + 4 + 5 = 12 Subarray 4: {4

Make sum of all subarrays of length K equal by only inserting elements

Given an array arr[] of length N such that (1 <= arr[i] <= N), the task is to modify the array, by only inserting elements within the range [1, N], such that the sum of all subarrays of length K become equal. Print the modified array, if possible. Else print "Not possible".Examples: Input: arr[] = {1, 2, 2, 1}, K = 2 Output: 1 2 1 2 1 Explana

Generate a unique Array of length N with sum of all subarrays divisible by N

Given an integer N, the task is to make an array of unique elements of length N such that all subarrays sum modulo N equals to zero. Examples: Input: N = 6 Output: 6 12 18 24 30 36 Explanation: Since all elements are a multiple of 6. Hence all subarrays add up to a sum divisible by 6.Input: N = 4 Output: 4 8 12 16 Approach: We can observe that for

Minimize the Sum of all the subarrays made up of the products of same-indexed elements

Given two arrays arr[] and arr2[] of length N, the task is to find the minimum sum of all the subarrays made up of the products of the same indexed elements of both the arrays after rearranging the second array. Note: Since the answer can be very large, print the answer modulo 109 + 7. Examples: Input: arr[] = {1, 2}, arr2[] = {2, 3} Output: 14 Exp

Rearrange array to make sum of all subarrays starting from first index non-zero

Given an array arr[] consisting of N integers, the task is to rearrange the array such that sum of all subarrays starting from the first index of the array is non-zero. If it is not possible to generate such arrangement, then print "-1". Examples: Input: arr[] = {-1, 1, -2, 3}Output: {-1, -2, 1, 3}Explanation: One of the possible rearrangement is {

Sum of products of all possible Subarrays

Given an array arr[] of N positive integers, the task is to find the sum of the product of elements of all the possible subarrays. Examples: Input: arr[] = {1, 2, 3}Output: 20Explanation: Possible Subarrays are: {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 2, 3}.Products of all the above subarrays are 1, 2, 3, 2, 6 and 6 respectively.Sum of all products = 1

Sum of maximum of all subarrays by adding even frequent maximum twice

Given an array arr[] consisting of N integers (All array elements are a perfect power of 2), the task is to calculate the sum of the maximum elements in all the subarrays. Note: If the frequency of the maximum element in a subarray is even, add twice the value of that element to the sum. Examples: Input: arr[] = {1, 2}Output: 5Explanation: All poss

Find two non-intersecting subarrays having equal sum of all elements raised to the power of 2

Given an array arr[] of positive integers of size N, the task is to check if there exists two non-intersecting subarrays in arr[] such that sum of all possible 2(subarr[i]) and the sum of all possible 2(subarr2[j]) are equal. Examples: Input: arr[] = {4, 3, 0, 1, 2, 0}Output: YESExplanation: Expressing every array element in the form of 2arr[i], th

Minimum replacements required to make sum of all K-length subarrays equal

Given an array arr[] consisting of N positive integers and an integer K, the task is to make the sum of all K-length subarrays equal by replacing minimum number of array elements with any integer. Examples: Input: arr[] = {3, 4, 3, 5, 6}, K = 2Output: 2Explanation: Operation 1: Replacing arr[3] by 4 modifies arr[] to {3, 4, 3, 4, 6}.Operation 2: Re

Maximize product of min value of subarray and sum of subarray over all subarrays of length K

Given an array arr[] of N integers, the task is to find the maximum possible value of (min * sum) among all possible subarrays having K elements, where min denotes the smallest integer of the subarray and sum denotes the sum of all elements of the subarray. Example: Input: arr[] = {1, 2, 3, 2}, K = 3Output: 14Explanation: For the subarray {2, 3, 2}

Find the sum of medians of all odd length subarrays

Given an array arr[] of size N, the task is to find the sum of medians of all sub-array of odd-length. Examples: Input: arr[] = {4, 2, 5, 1}Output: 18Explanation : Sub-Arrays of odd length and their medians are : [4] -> Median is 4[4, 2, 5] -> Median is 4[2] -> Median is 2[2, 5, 1] -> Median is 2[5] -> Median is 5[1] -> Median is

Article Tags :

DSA
Hash

Practice Tags :

Hash