Given an array arr[] of integer elements, the task is to find the length of the longest sub-array whose product is 0.
Examples:
Input: arr[] = {1, 2, 3, 0, 1, 2, 0}
Output: 7
{1, 2, 3, 0, 1, 2, 0} is the longest sub-array whose product is 0.
Input: arr[] = {1, 2, 3, 4, 5}
Output: 0
There is no sub-array possible whose product is 0.
Approach:
- If there is no element in the array which is equal to 0 then there will be no sub-array possible whose product is 0.
- If there is at least one element in the array which is equal to 0 then the longest sub-array whose product is 0 will be the complete array.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the length of the// longest sub-array whose product// of elements is 0int longestSubArray(int arr[], int n){ bool isZeroPresent = false; for (int i = 0; i < n; i++) { if (arr[i] == 0) { isZeroPresent = true; break; } } if (isZeroPresent) return n; return 0;}// Driver codeint main(){ int arr[] = { 1, 2, 3, 0, 1, 2, 0 }; int n = sizeof(arr) / sizeof(arr[0]); cout << longestSubArray(arr, n); return 0;} |
Java
// Java implementation of the approachclass GFG { // Function to return the length of the // longest sub-array whose product // of elements is 0 static int longestSubArray(int arr[], int n) { boolean isZeroPresent = false; for (int i = 0; i < n; i++) { if (arr[i] == 0) { isZeroPresent = true; break; } } if (isZeroPresent) return n; return 0; } // Driver code public static void main(String args[]) { int arr[] = { 1, 2, 3, 0, 1, 2, 0 }; int n = arr.length; System.out.print(longestSubArray(arr, n)); }} |
Python3
# Python3 implementation of the approach# Function to return the length of # the longest sub-array whose product# of elements is 0def longestSubArray(arr, n) : isZeroPresent = False for i in range (0 , n) : if (arr[i] == 0) : isZeroPresent = True break if (isZeroPresent) : return n return 0# Driver codearr = [ 1, 2, 3, 0, 1, 2, 0 ]n = len(arr)print(longestSubArray(arr, n))# This code is contributed by ihritik |
C#
// C# implementation of the approachusing System;class GFG { // Function to return the length of the // longest sub-array whose product // of elements is 0 static int longestSubArray(int[] arr, int n) { bool isZeroPresent = false; for (int i = 0; i < n; i++) { if (arr[i] == 0) { isZeroPresent = true; break; } } if (isZeroPresent) return n; return 0; } // Driver code public static void Main() { int[] arr = { 1, 2, 3, 0, 1, 2, 0 }; int n = arr.Length; Console.Write(longestSubArray(arr, n)); }} |
Javascript
<script>// Javascript implementation of the approach// Function to return the length of the// longest sub-array whose product// of elements is 0function longestSubArray(arr, n){ var isZeroPresent = false; for (var i = 0; i < n; i++) { if (arr[i] == 0) { isZeroPresent = true; break; } } if (isZeroPresent) return n; return 0;}// Driver codevar arr = [ 1, 2, 3, 0, 1, 2, 0 ];var n = arr.length;document.write(longestSubArray(arr, n));// This code is contributed by rutvik_56.</script> |
PHP
<?php// PHP implementation of the approach// Function to return the length of the// longest sub-array whose product// of elements is 0function longestSubArray($arr, $n){ $isZeroPresent = false; for ($i = 0; $i < $n; $i++) { if ($arr[$i] == 0) { $isZeroPresent = true; break; } } if ($isZeroPresent) return $n; return 0;}// Driver code$arr = array( 1, 2, 3, 0, 1, 2, 0 );$n = sizeof($arr);echo longestSubArray($arr, $n);// This code is contributed by ihritik?> |
Output
7
Time Complexity: O(n), where n represents the size of the given array.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Method2:Using Hashing(unordered Map)
Approach:
1. We can use an unordered_map to store the frequency of elements in the array.
2. If the map contains a 0, then the entire array is a sub-array whose product is 0, so we return n.
3. Otherwise, there is no sub-array whose product is 0, so we return 0.
Implementation:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the length of the// longest sub-array whose product// of elements is 0int longestSubArray(int arr[], int n){ unordered_map<int,int>mp; for(int i=0;i<n;i++) { mp[arr[i]]++; } if(mp[0]) return n; else return 0;}// Driver codeint main(){ int arr[] = { 1, 2, 3, 0, 1, 2, 0}; int n = sizeof(arr) / sizeof(arr[0]); cout<<longestSubArray(arr, n); return 0;} |
Java
import java.util.HashMap;public class LongestSubArray { // Function to return the length of the // longest sub-array whose product // of elements is 0 static int longestSubArray(int[] arr, int n) { HashMap<Integer, Integer> mp = new HashMap<>(); for (int i = 0; i < n; i++) { mp.put(arr[i], mp.getOrDefault(arr[i], 0) + 1); } if (mp.containsKey(0)) { return n; } else { return 0; } } // Driver code public static void main(String[] args) { int[] arr = {1, 2, 3, 0, 1, 2, 0}; int n = arr.length; System.out.println(longestSubArray(arr, n)); }} |
Python3
from collections import defaultdictdef longestSubArray(arr, n): mp = defaultdict(int) for i in range(n): mp[arr[i]] += 1 if mp[0]: return n else: return 0arr = [1, 2, 3, 0, 1, 2, 0]n = len(arr)print(longestSubArray(arr, n)) |
C#
using System;using System.Collections.Generic;class Program{ // Function to return the length of the // longest sub-array whose product // of elements is 0 static int LongestSubArray(int[] arr, int n) { Dictionary<int, int> mp = new Dictionary<int, int>(); for (int i = 0; i < n; i++) { if (mp.ContainsKey(arr[i])) { mp[arr[i]]++; } else { mp[arr[i]] = 1; } } if (mp.ContainsKey(0)) { return n; } else { return 0; } } // Driver code static void Main() { int[] arr = { 1, 2, 3, 0, 1, 2, 0 }; int n = arr.Length; Console.WriteLine(LongestSubArray(arr, n)); // Uncomment the line below if running in Visual Studio or an environment that doesn't automatically pause // Console.ReadLine(); }}// This code is contributed by Dwaipayan Bandyopadhyay |
Javascript
function longestSubArray(arr, n) { let mp = new Map(); for (let i = 0; i < n; i++) { if (mp.has(arr[i])) { mp.set(arr[i], mp.get(arr[i]) + 1); } else { mp.set(arr[i], 1); } } if (mp.has(0)) { return n; } else { return 0; }}let arr = [1, 2, 3, 0, 1, 2, 0];let n = arr.length;console.log(longestSubArray(arr, n)); |
Output
7
Time Complexity: O(n), where n represents the size of the given array.
Auxiliary Space: O(n), we use extra space as an unordered map.
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!
