Given an array arr[] and an integer X, the task is to print the longest subarray such that the sum of its elements isn’t divisible by X. If no such subarray exists, print “-1”.
Note: If more than one subarray exists with the given property, print any one of them.
Examples:
Input: arr[] = {1, 2, 3} X = 3
Output: 2 3
Explanation:
The subarray {2, 3} has a sum of elements 5, which isn’t divisible by 3.
Input: arr[] = {2, 6} X = 2
Output: -1
Explanation:
All possible subarrays {1}, {2}, {1, 2} have an even sum.
Therefore, the answer is -1.
Naive Approach: The simplest approach to solve the problem is to generate all possible subarrays and keep calculating its sum. If any subarray is found to have sum not divisible by X, compare the length with maximum length obtained(maxm) and update the maxm accordingly and update the starting index and ending index of the subarray. Finally, print the subarray having the stored starting and ending indices. If there is no such subarray then print “-1”.
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to print the longest// subarray with sum of elements// not divisible by Xvoid max_length(int n, int x,vector<int> a){ // Variable to store start and end index int maxm = -1, start = -1, end = -1; // traversing to generate all subarray for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { // variable to store sum int sum = 0; for (int k = i; k <= j; k++) { sum += a[k]; } // Checking if sum is divisible by x // or not. If not then update the length // if it greater than all previous length if (sum % x != 0 && j - i + 1 > maxm) { maxm = j - i + 1; start = i; end = j; } } } // If there is no such subarray then print “-1” if (maxm == -1) { cout << "-1\n"; } // print the subarray having the stored starting and ending indices else { for (int i = start; i <= end; i++) { cout << a[i] << " "; } cout << "\n"; }}// Driver Codeint main(){ int x = 3; vector<int> v = { 1, 3, 2, 6 }; int N = v.size(); max_length(N, x, v); return 0;}// This code is contributed by Pushpesh Raj. |
Java
// Java Program to implement// the above approachimport java.util.*;class Main { // Function to print the longest // subarray with sum of elements // not divisible by X static void max_length(int n, int x, ArrayList<Integer> a) { // Variable to store start and end index int maxm = -1, start = -1, end = -1; // traversing to generate all subarray for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { // variable to store sum int sum = 0; for (int k = i; k <= j; k++) { sum += a.get(k); } // Checking if sum is divisible by x // or not. If not then update the length // if it greater than all previous length if (sum % x != 0 && j - i + 1 > maxm) { maxm = j - i + 1; start = i; end = j; } } } // If there is no such subarray then print “-1” if (maxm == -1) { System.out.println("-1"); } // print the subarray having the stored starting and // ending indices else { for (int i = start; i <= end; i++) { System.out.print(a.get(i) + " "); } System.out.println(); } } // Driver Code public static void main(String[] args) { int x = 3; ArrayList<Integer> v = new ArrayList<Integer>( Arrays.asList(1, 3, 2, 6)); int N = v.size(); max_length(N, x, v); }} |
Python3
# Python Program to implement# the above approachdef max_length(n, x, a): # Variable to store start and end index maxm = -1 start = -1 end = -1 # traversing to generate all subarray for i in range(0, n): for j in range(i, n): # variable to store sum sum1 = 0 for k in range(i, j + 1): sum1 += a[k] # Checking if sum is divisible by x # or not. If not then update the length # if it greater than all previous length if sum1 % x != 0 and j - i + 1 > maxm: maxm = j - i + 1 start = i end = j # If there is no such subarray then print “-1” if maxm == -1: print("-1") # print the subarray having the stored starting and ending indices else: for i in range(start, end + 1): print(a[i], end=" ") print()# Driver Codeif __name__ == "__main__": x = 3 v = [1, 3, 2, 6] N = len(v) max_length(N, x, v) |
C#
// C# Program to implement// the above approachusing System;using System.Collections.Generic;using System.Linq;class GFG { // Function to print the longest // subarray with sum of elements // not divisible by X static void max_length(int n, int x, List<int> a) { // Variable to store start and end index int maxm = -1, start = -1, end = -1; // traversing to generate all subarray for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { // variable to store sum int sum = 0; for (int k = i; k <= j; k++) { sum += a[k]; } // Checking if sum is divisible by x // or not. If not then update the length // if it greater than all previous length if (sum % x != 0 && j - i + 1 > maxm) { maxm = j - i + 1; start = i; end = j; } } } // If there is no such subarray then print “-1” if (maxm == -1) { Console.WriteLine("-1"); } // print the subarray having the stored starting and // ending indices else { for (int i = start; i <= end; i++) { Console.Write(a[i] + " "); } Console.WriteLine(); } } // Driver Code static void Main(string[] args) { int x = 3; List<int> v = new List<int>{ 1, 3, 2, 6 }; int N = v.Count; max_length(N, x, v); }} |
Javascript
// JavaScript program to implement// the above approachfunction max_length(n, x, a) { // Variable to store start and end index let maxm = -1; let start = -1; let end = -1; // traversing to generate all subarray for (let i = 0; i < n; i++) { for (let j = i; j < n; j++) { // variable to store sum let sum1 = 0; for (let k = i; k <= j; k++) { sum1 += a[k]; } // Checking if sum is divisible by x // or not. If not then update the length // if it greater than all previous length if (sum1 % x !== 0 && j - i + 1 > maxm) { maxm = j - i + 1; start = i; end = j; } } } // If there is no such subarray then print “-1” if (maxm === -1) { console.log("-1"); } // print the subarray having the stored starting and ending indices else { temp="" for (let i = start; i <= end; i++) { temp = temp + a[i]+" "; } console.log(temp); }}// Driver Codelet x = 3;let v = [1, 3, 2, 6];let N = v.length;max_length(N, x, v); |
Output
3 2 6
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach we will find the prefix and suffix array sum. Follow the steps below:
- Generate the prefix sum array and suffix sum array.
- Iterate from [0, N – 1] using Two Pointers and choose the prefix and suffix sum of the element at each index which is not divisible by X. Store the starting index and ending index of the subarray.
- After completing the above steps, if there exist a subarray with sum not divisible by X, then print the subarray having the stored starting and ending indices.
- If there is no such subarray then print “-1”.
Below is the implementation of the above approach:
C++
#include <iostream>// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to print the longest// subarray with sum of elements// not divisible by Xvoid max_length(int N, int x, vector<int>& v){ int i, a; // Pref[] stores the prefix sum // Suff[] stores the suffix sum vector<int> preff, suff; int ct = 0; for (i = 0; i < N; i++) { a = v[i]; // If array element is // divisibile by x if (a % x == 0) { // Increase count ct += 1; } } // If all the array elements // are divisible by x if (ct == N) { // No subarray possible cout << -1 << endl; return; } // Reverse v to calculate the // suffix sum reverse(v.begin(), v.end()); suff.push_back(v[0]); // Calculate the suffix sum for (i = 1; i < N; i++) { suff.push_back(v[i] + suff[i - 1]); } // Reverse to original form reverse(v.begin(), v.end()); // Reverse the suffix sum array reverse(suff.begin(), suff.end()); preff.push_back(v[0]); // Calculate the prefix sum for (i = 1; i < N; i++) { preff.push_back(v[i] + preff[i - 1]); } int ans = 0; // Stores the starting index // of required subarray int lp = 0; // Stores the ending index // of required subarray int rp = N - 1; for (i = 0; i < N; i++) { // If suffix sum till i-th // index is not divisible by x if (suff[i] % x != 0 && (ans < (N - 1))) { lp = i; rp = N - 1; // Update the answer ans = max(ans, N - i); } // If prefix sum till i-th // index is not divisible by x if (preff[i] % x != 0 && (ans < (i + 1))) { lp = 0; rp = i; // Update the answer ans = max(ans, i + 1); } } // Print the longest subarray for (i = lp; i <= rp; i++) { cout << v[i] << " "; }}// Driver Codeint main(){ int x = 3; vector<int> v = { 1, 3, 2, 6 }; int N = v.size(); max_length(N, x, v); return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{// Function to print the longest// subarray with sum of elements// not divisible by Xstatic void max_length(int N, int x, int []v){ int i, a; // Pref[] stores the prefix sum // Suff[] stores the suffix sum List<Integer> preff = new Vector<Integer>(); List<Integer> suff = new Vector<Integer>(); int ct = 0; for(i = 0; i < N; i++) { a = v[i]; // If array element is // divisibile by x if (a % x == 0) { // Increase count ct += 1; } } // If all the array elements // are divisible by x if (ct == N) { // No subarray possible System.out.print(-1 + "\n"); return; } // Reverse v to calculate the // suffix sum v = reverse(v); suff.add(v[0]); // Calculate the suffix sum for(i = 1; i < N; i++) { suff.add(v[i] + suff.get(i - 1)); } // Reverse to original form v = reverse(v); // Reverse the suffix sum array Collections.reverse(suff); preff.add(v[0]); // Calculate the prefix sum for(i = 1; i < N; i++) { preff.add(v[i] + preff.get(i - 1)); } int ans = 0; // Stores the starting index // of required subarray int lp = 0; // Stores the ending index // of required subarray int rp = N - 1; for(i = 0; i < N; i++) { // If suffix sum till i-th // index is not divisible by x if (suff.get(i) % x != 0 && (ans < (N - 1))) { lp = i; rp = N - 1; // Update the answer ans = Math.max(ans, N - i); } // If prefix sum till i-th // index is not divisible by x if (preff.get(i) % x != 0 && (ans < (i + 1))) { lp = 0; rp = i; // Update the answer ans = Math.max(ans, i + 1); } } // Print the longest subarray for(i = lp; i <= rp; i++) { System.out.print(v[i] + " "); }}static int[] reverse(int a[]) { int i, n = a.length, t; for(i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } return a;}// Driver Codepublic static void main(String[] args){ int x = 3; int []v = { 1, 3, 2, 6 }; int N = v.length; max_length(N, x, v);}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to implement # the above approach # Function to print the longest # subarray with sum of elements # not divisible by X def max_length(N, x, v): # Pref[] stores the prefix sum # Suff[] stores the suffix sum preff, suff = [], [] ct = 0 for i in range(N): a = v[i] # If array element is # divisibile by x if a % x == 0: # Increase count ct += 1 # If all the array elements # are divisible by x if ct == N: # No subarray possible print(-1) return # Reverse v to calculate the # suffix sum v.reverse() suff.append(v[0]) # Calculate the suffix sum for i in range(1, N): suff.append(v[i] + suff[i - 1]) # Reverse to original form v.reverse() # Reverse the suffix sum array suff.reverse() preff.append(v[0]) # Calculate the prefix sum for i in range(1, N): preff.append(v[i] + preff[i - 1]) ans = 0 # Stores the starting index # of required subarray lp = 0 # Stores the ending index # of required subarray rp = N - 1 for i in range(N): # If suffix sum till i-th # index is not divisible by x if suff[i] % x != 0 and ans < N - 1: lp = i rp = N - 1 # Update the answer ans = max(ans, N - i) # If prefix sum till i-th # index is not divisible by x if preff[i] % x != 0 and ans < i + 1: lp = 0 rp = i # Update the answer ans = max(ans, i + 1) # Print the longest subarray for i in range(lp, rp + 1): print(v[i], end = " ") # Driver codex = 3v = [ 1, 3, 2, 6 ]N = len(v)max_length(N, x, v)# This code is contributed by Stuti Pathak |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{// Function to print the longest// subarray with sum of elements// not divisible by Xstatic void max_length(int N, int x, int []v){ int i, a; // Pref[] stores the prefix sum // Suff[] stores the suffix sum List<int> preff = new List<int>(); List<int> suff = new List<int>(); int ct = 0; for(i = 0; i < N; i++) { a = v[i]; // If array element is // divisibile by x if (a % x == 0) { // Increase count ct += 1; } } // If all the array elements // are divisible by x if (ct == N) { // No subarray possible Console.Write(-1 + "\n"); return; } // Reverse v to calculate the // suffix sum v = reverse(v); suff.Add(v[0]); // Calculate the suffix sum for(i = 1; i < N; i++) { suff.Add(v[i] + suff[i - 1]); } // Reverse to original form v = reverse(v); // Reverse the suffix sum array suff.Reverse(); preff.Add(v[0]); // Calculate the prefix sum for(i = 1; i < N; i++) { preff.Add(v[i] + preff[i - 1]); } int ans = 0; // Stores the starting index // of required subarray int lp = 0; // Stores the ending index // of required subarray int rp = N - 1; for(i = 0; i < N; i++) { // If suffix sum till i-th // index is not divisible by x if (suff[i] % x != 0 && (ans < (N - 1))) { lp = i; rp = N - 1; // Update the answer ans = Math.Max(ans, N - i); } // If prefix sum till i-th // index is not divisible by x if (preff[i] % x != 0 && (ans < (i + 1))) { lp = 0; rp = i; // Update the answer ans = Math.Max(ans, i + 1); } } // Print the longest subarray for(i = lp; i <= rp; i++) { Console.Write(v[i] + " "); }}static int[] reverse(int []a) { int i, n = a.Length, t; for(i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } return a;}// Driver Codepublic static void Main(String[] args){ int x = 3; int []v = { 1, 3, 2, 6 }; int N = v.Length; max_length(N, x, v);}}// This code is contributed by PrinciRaj1992 |
Javascript
// JS Program to implement// the above approach// Function to print the longest// subarray with sum of elements// not divisible by Xfunction max_length( N, x, v){ let i, a; // Pref[] stores the prefix sum // Suff[] stores the suffix sum let preff = [], suff = []; let ct = 0; for (i = 0; i < N; i++) { a = v[i]; // If array element is // divisibile by x if (a % x == 0) { // Increase count ct += 1; } } // If all the array elements // are divisible by x if (ct == N) { // No subarray possible console.log(-1) return; } // Reverse v to calculate the // suffix sum v.reverse() suff.push(v[0]); // Calculate the suffix sum for (i = 1; i < N; i++) { suff.push(v[i] + suff[i - 1]); } // Reverse to original form v.reverse() // Reverse the suffix sum array suff.reverse() preff.push(v[0]); // Calculate the prefix sum for (i = 1; i < N; i++) { preff.push(v[i] + preff[i - 1]); } let ans = 0; // Stores the starting index // of required subarray let lp = 0; // Stores the ending index // of required subarray let rp = N - 1; for (i = 0; i < N; i++) { // If suffix sum till i-th // index is not divisible by x if (suff[i] % x != 0 && (ans < (N - 1))) { lp = i; rp = N - 1; // Update the answer ans = Math.max(ans, N - i); } // If prefix sum till i-th // index is not divisible by x if (preff[i] % x != 0 && (ans < (i + 1))) { lp = 0; rp = i; // Update the answer ans = Math.max(ans, i + 1); } } // Print the longest subarray for (i = lp; i <= rp; i++) { process.stdout.write(v[i] + " "); }}// Driver Codelet x = 3;let v = [ 1, 3, 2, 6 ];let N = v.length;max_length(N, x, v);// This code is contributed by phasing17 |
Output:
3 2 6
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
