Given an array arr[] consisting of positive numbers, the task is to find the maximum range [L, R] whose sum is divisible by M. If there is no range present return -1. Examples:
Input: arr[] = {3, 7, 5, 2, 5, 10}, M = 3 Output: 1 3 Explanation: Sum of numbers from 1 to 3 is 3+7+5 which is 15. Input : A[] = {4, 8, 12, 16, 20} M = 11 Output : -1
Naive Approach: A naive approach is that we can iterate through all possible L and R in the array and check if the sum is divisible. If it is, then store the length of the array. Efficient Approach: The idea here is to use a prefix sum array.
- Initially, the prefix sum of the values is calculated.
- Once the prefix sum is calculated, every value is replaced by the value modulo M.
- The indices where the final value is equal is the range where the sum is perfectly divisible by M.
- The maximum range of the same values is found.
Below is the implementation of the above approach,
CPP
// C++ implementation of the above approach. #include <bits/stdc++.h> using namespace std; // Function to find the maximum range // whose sum is divisible by M. pair<int, int> maxrange(int n, int a[], int m) { int pre[n + 5]; map<int, set<int> > mpp; int value, l, r, lans = -1, rans = -1, ans = 0; // Calculate the prefix sum pre[0] = a[0]; for (int i = 1; i < n; i++) { pre[i] = a[i] + pre[i - 1]; } // Replacing the values with modulo M // and inserting the indices into the map for (int i = 0; i < n; i++) { pre[i] = pre[i] % m; mpp[pre[i]].insert(i); } // Calculate the range [L, R] for (auto it = mpp.begin(); it != mpp.end(); it++) { if (it->first == 0) { value = *((it->second).rbegin()) + 1; l = 1; r = value; } else { value = *((it->second).rbegin()) - *((it->second.begin())); l = *((it->second.begin())) + 2; r = *((it->second).rbegin()) + 1; } if (value > ans && l <= r) { ans = value; lans = l; rans = r; } } return make_pair(lans, rans); } // Driver code int main() { int A[] = { 3, 7, 5, 2, 5, 10 }; int N = sizeof(A) / sizeof(A[0]); int M = 3; pair<int, int> value = maxrange(N, A, M); if (value.first == -1) { cout << -1 << "\n"; } else { cout << value.first << " " << value.second << "\n"; } return 0; } |
Java
import java.util.*;class GFG { // Function to find the maximum range // whose sum is divisible by M. static Pair<Integer, Integer> maxRange(int n, int[] a, int m) { int[] pre = new int[n + 5]; TreeMap<Integer, TreeSet<Integer>> mpp = new TreeMap<>(); int value, l, r, lans = -1, rans = -1, ans = 0; // Calculate the prefix sum pre[0] = a[0]; for (int i = 1; i < n; i++) { pre[i] = a[i] + pre[i - 1]; } // Replacing the values with modulo M // and inserting the indices into the map for (int i = 0; i < n; i++) { pre[i] = pre[i] % m; if (!mpp.containsKey(pre[i])) { mpp.put(pre[i], new TreeSet<>()); } mpp.get(pre[i]).add(i); } // Calculate the range [L, R] for (Map.Entry<Integer, TreeSet<Integer>> entry : mpp.entrySet()) { int key = entry.getKey(); TreeSet<Integer> indices = entry.getValue(); if (key == 0) { value = indices.last() + 1; l = 1; r = value; } else { value = indices.last() - indices.first(); l = indices.first() + 2; r = indices.last() + 1; } if (value > ans && l <= r) { ans = value; lans = l; rans = r; } } return new Pair<>(lans, rans); } // Driver code public static void main(String[] args) { int[] A = { 3, 7, 5, 2, 5, 10 }; int N = A.length; int M = 3; Pair<Integer, Integer> value = maxRange(N, A, M); if (value.getKey() == -1) { System.out.println(-1); } else { System.out.println(value.getKey() + " " + value.getValue()); } } // Pair class to represent a pair of values static class Pair<T, U> { T first; U second; public Pair(T first, U second) { this.first = first; this.second = second; } public T getKey() { return first; } public U getValue() { return second; } }} |
Python3
# Function to find the maximum range# whose sum is divisible by M.def maxrange(n, a, m): pre = [0] * (n + 5) mpp = {} value, l, r, lans, rans, ans = -1, -1, -1, 0, 0, 0 # Calculate the prefix sum pre[0] = a[0] for i in range(1, n): pre[i] = a[i] + pre[i - 1] # Replacing the values with modulo M # and inserting the indices into the map for i in range(n): pre[i] = pre[i] % m if pre[i] not in mpp: mpp[pre[i]] = set() mpp[pre[i]].add(i) # Calculate the range [L, R] for key in mpp: if key == 0: value = max(mpp[key]) + 1 l, r = 1, value else: value = max(mpp[key]) - min(mpp[key]) l, r = min(mpp[key]) + 2, max(mpp[key]) + 1 if value > ans and l <= r: ans = value lans = l rans = r return (lans, rans)# Driver codeA = [3, 7, 5, 2, 5, 10]N = len(A)M = 3value = maxrange(N, A, M)if value[0] == -1: print(-1)else: print(value[0], value[1]) # This code is contributed by shiv1o43g |
C#
using System;using System.Collections.Generic;class GFG{ // Function to find the maximum range // whose sum is divisible by M. static (int, int) MaxRange(int n, int[] a, int m) { int[] pre = new int[n + 5]; SortedDictionary<int, SortedSet<int>> mpp = new SortedDictionary<int, SortedSet<int>>(); int value, l, r, lans = -1, rans = -1, ans = 0; // Calculate the prefix sum pre[0] = a[0]; for (int i = 1; i < n; i++) { pre[i] = a[i] + pre[i - 1]; } // Replacing the values with modulo M // and inserting the indices into the map for (int i = 0; i < n; i++) { pre[i] = pre[i] % m; if (!mpp.ContainsKey(pre[i])) { mpp[pre[i]] = new SortedSet<int>(); } mpp[pre[i]].Add(i); } // Calculate the range [L, R] foreach (var entry in mpp) { int key = entry.Key; SortedSet<int> indices = entry.Value; if (key == 0) { value = indices.Max + 1; l = 1; r = value; } else { value = indices.Max - indices.Min; l = indices.Min + 2; r = indices.Max + 1; } if (value > ans && l <= r) { ans = value; lans = l; rans = r; } } return (lans, rans); } // Driver code public static void Main(string[] args) { int[] A = { 3, 7, 5, 2, 5, 10 }; int N = A.Length; int M = 3; var value = MaxRange(N, A, M); if (value.Item1 == -1) { Console.WriteLine(-1); } else { Console.WriteLine($"{value.Item1} {value.Item2}"); } }} |
Javascript
// Function to find the maximum range // whose sum is divisible by M.function maxRange(n, a, m) { let pre = new Array(n + 5).fill(0); let mpp = {}; let value = -1; let l = -1; let r = -1; let lans = 0; let rans = 0; let ans = 0; // Calculate the prefix sum pre[0] = a[0]; for (let i = 1; i < n; i++) { pre[i] = a[i] + pre[i - 1]; } // Replacing the values with modulo M // and inserting the indices into the map for (let i = 0; i < n; i++) { pre[i] = pre[i] % m; if (!mpp[pre[i]]) { mpp[pre[i]] = new Set(); } mpp[pre[i]].add(i); } // Calculate the range [L, R] for (let key in mpp) { key = parseInt(key); if (key === 0) { value = Math.max(...mpp[key]) + 1; l = 1; r = value; } else { value = Math.max(...mpp[key]) - Math.min(...mpp[key]); l = Math.min(...mpp[key]) + 2; r = Math.max(...mpp[key]) + 1; } if (value > ans && l <= r) { ans = value; lans = l; rans = r; } } return [lans, rans];}// Driver codeconst A = [3, 7, 5, 2, 5, 10];const N = A.length;const M = 3;const value = maxRange(N, A, M);if (value[0] === -1) { console.log(-1);} else { console.log(value[0], value[1]);} |
Output
1 3
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
