Dada una array arr[] que consta de N enteros, la tarea es comprobar si todos los subarreglos de la array tienen al menos un elemento único o no. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: arr[] = {1, 2, 1}
Salida: Sí
Explicación:
Para subarreglos de tamaño 1: {1}, {2}, {1}, la condición siempre será verdadera.
Para subarreglos de tamaño 2: {1, 2}, {2, 1}, cada subarreglo tiene al menos un elemento único.
Para subarreglos de tamaño 3 = {1, 2, 1}, en este subarreglo tenemos 2 como único elemento único.
Dado que cada subarreglo tiene al menos un elemento único, imprima «Sí».Entrada: arr[] = {1, 2, 3, 1, 2, 3}
Salida: No
Explicación:
Los subarreglos de tamaño 6: {1, 2, 3, 1, 2, 3} no contienen ningún elemento único. Por lo tanto, escriba “No”.
Enfoque ingenuo: el enfoque más simple es generar todos los subarreglos y usar HashMap para cada subarreglo para almacenar la frecuencia de cada elemento de ese subarreglo. Si algún subarreglo no tiene al menos un elemento único, imprima «No» . De lo contrario, escriba «Sí» .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for above approach
#include<bits/stdc++.h>
using namespace std;
// Function to check if all subarrays
// of array have at least one unique element
string check(int arr[], int n)
{
// Stores frequency of subarray
// elements
map<int, int> hm;
// Generate all subarrays
for(int i = 0; i < n; i++)
{
// Insert first element in map
hm[arr[i]] = 1;
for(int j = i + 1; j < n; j++)
{
// Update frequency of current
// subarray in the HashMap
hm[arr[j]]++;
bool flag = false;
// Check if at least one element
// occurs once in current subarray
for(auto x : hm)
{
if (x.second == 1)
{
flag = true;
break;
}
}
// If any subarray doesn't
// have unique element
if (!flag)
return "No";
}
// Clear map for next subarray
hm.clear();
}
// Return Yes if all subarray
// having at least 1 unique element
return "Yes";
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 2, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << check(arr, N);
}
// This code is contributed by bgangwar59
Java
// Java program for above approach
import java.util.*;
import java.lang.*;
class GFG {
// Function to check if all subarrays
// of array have at least one unique element
static String check(int arr[], int n)
{
// Stores frequency of subarray
// elements
Map<Integer, Integer> hm
= new HashMap<>();
// Generate all subarrays
for (int i = 0; i < n; i++) {
// Insert first element in map
hm.put(arr[i], 1);
for (int j = i + 1; j < n; j++) {
// Update frequency of current
// subarray in the HashMap
hm.put(
arr[j],
hm.getOrDefault(arr[j], 0) + 1);
boolean flag = false;
// Check if at least one element
// occurs once in current subarray
for (Integer k : hm.values()) {
if (k == 1) {
flag = true;
break;
}
}
// If any subarray doesn't
// have unique element
if (!flag)
return "No";
}
// Clear map for next subarray
hm.clear();
}
// Return Yes if all subarray
// having at least 1 unique element
return "Yes";
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int[] arr = { 1, 2, 1 };
int N = arr.length;
// Function Call
System.out.println(check(arr, N));
}
}
Python3
# Python3 program for # the above approach from collections import defaultdict # Function to check if # all subarrays of array # have at least one unique # element def check(arr, n): # Stores frequency of # subarray elements hm = defaultdict (int) # Generate all subarrays for i in range(n): # Insert first element # in map hm[arr[i]] += 1 for j in range(i + 1, n): # Update frequency of # current subarray in # the HashMap hm[arr[j]] += 1 flag = False # Check if at least one # element occurs once in # current subarray for k in hm.values(): if (k == 1): flag = True break # If any subarray doesn't # have unique element if (not flag): return "No" # Clear map for next # subarray hm.clear() # Return Yes if all # subarray having at # least 1 unique element return "Yes" # Driver Code if __name__ == "__main__": # Given array arr[] arr = [1, 2, 1] N = len(arr) # Function Call print(check(arr, N)) # This code is contributed by Chitranayal
C#
// C# program for the
// above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to check if all
// subarrays of array have at
// least one unique element
static String check(int []arr,
int n)
{
// Stores frequency of
// subarray elements
Dictionary<int,
int> hm =
new Dictionary<int,
int>();
// Generate all subarrays
for (int i = 0; i < n; i++)
{
// Insert first element
// in map
hm.Add(arr[i], 1);
for (int j = i + 1; j < n; j++)
{
// Update frequency of current
// subarray in the Dictionary
if(hm.ContainsKey(arr[j]))
hm[arr[j]]++;
else
hm.Add(arr[j], 1);
bool flag = false;
// Check if at least one
// element occurs once
// in current subarray
foreach (int k in hm.Values)
{
if (k == 1)
{
flag = true;
break;
}
}
// If any subarray doesn't
// have unique element
if (!flag)
return "No";
}
// Clear map for next
// subarray
hm.Clear();
}
// Return Yes if all subarray
// having at least 1 unique
// element
return "Yes";
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int[] arr = {1, 2, 1};
int N = arr.Length;
// Function Call
Console.WriteLine(check(arr, N));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program for above approach
// Function to check if all subarrays
// of array have at least one unique element
function check(arr, n)
{
// Stores frequency of subarray
// elements
var hm = new Map();
// Generate all subarrays
for(var i = 0; i < n; i++)
{
// Insert first element in map
hm.set(arr[i], 1);
for(var j = i + 1; j < n; j++)
{
// Update frequency of current
// subarray in the HashMap
if(hm.has(arr[j]))
hm.set(arr[j], hm.get(arr[j])+1);
else
hm.set(arr[j], 1)
var flag = false;
// Check if at least one element
// occurs once in current subarray
hm.forEach((value, key) => {
if (value == 1)
{
flag = true;
}
});
// If any subarray doesn't
// have unique element
if (!flag)
return "No";
}
// Clear map for next subarray
hm = new Map();
}
// Return Yes if all subarray
// having at least 1 unique element
return "Yes";
}
// Driver Code
// Given array arr[]
var arr = [1, 2, 1];
var N = arr.length;
// Function Call
document.write( check(arr, N));
</script>
Producción
Yes
Complejidad temporal: O(N 3 )
Espacio auxiliar: O(N)
Enfoque eficiente: siga los pasos a continuación para optimizar el enfoque anterior:
- Itere un ciclo sobre el rango [0, N – 1] y cree un mapa para almacenar la frecuencia de cada carácter presente en el subarreglo actual.
- Cree un conteo variable para verificar que el subarreglo tenga al menos un elemento con frecuencia 1 o no.
- Recorra la array arr[] y actualice la frecuencia de cada elemento en el mapa y actualice el conteo como:
- Si la frecuencia del elemento es 1 , entonces incremente el conteo .
- Si la frecuencia del elemento es 2 , disminuya la cuenta .
- En los pasos anteriores, si el valor de count es 0 , imprima «No» , ya que existe un subarreglo que no tiene ningún elemento único.
- Después de toda la iteración, si el valor de la cuenta es siempre positivo, imprima «Sí» .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to check if all subarrays
// have at least one unique element
string check(int arr[], int n)
{
// Generate all subarray
for(int i = 0; i < n; i++)
{
// Store frequency of
// subarray's elements
map<int, int> hm;
int count = 0;
// Traverse the array over
// the range [i, N]
for(int j = i; j < n; j++)
{
// Update frequency of
// current subarray in map
hm[arr[j]]++;
// Increment count
if (hm[arr[j]] == 1)
count++;
// Decrement count
if (hm[arr[j]] == 2)
count--;
if (count == 0)
return "No";
}
}
// If all subarrays have at
// least 1 unique element
return "Yes";
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 2, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << check(arr, N);
}
// This code is contributed by SURENDRA_GANGWAR
Java
// Java program for the above approach
import java.util.*;
import java.lang.*;
class GFG {
// Function to check if all subarrays
// have at least one unique element
static String check(int arr[], int n)
{
// Generate all subarray
for (int i = 0; i < n; i++) {
// Store frequency of
// subarray's elements
Map<Integer, Integer> hm
= new HashMap<>();
int count = 0;
// Traverse the array over
// the range [i, N]
for (int j = i; j < n; j++) {
// Update frequency of
// current subarray in map
hm.put(arr[j],
hm.getOrDefault(arr[j], 0) + 1);
// Increment count
if (hm.get(arr[j]) == 1)
count++;
// Decrement count
if (hm.get(arr[j]) == 2)
count--;
if (count == 0)
return "No";
}
}
// If all subarrays have at
// least 1 unique element
return "Yes";
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int[] arr = { 1, 2, 1 };
int N = arr.length;
// Function Call
System.out.println(check(arr, N));
}
}
Python3
# Python3 program for the above approach
# Function to check if all subarrays
# have at least one unique element
def check(arr, n):
# Generate all subarray
for i in range(n):
# Store frequency of
# subarray's elements
hm = {}
count = 0
# Traverse the array over
# the range [i, N]
for j in range(i, n):
# Update frequency of
# current subarray in map
hm[arr[j]] = hm.get(arr[j], 0) + 1
# Increment count
if (hm[arr[j]] == 1):
count += 1
# Decrement count
if (hm[arr[j]] == 2):
count -= 1
if (count == 0):
return "No"
# If all subarrays have at
# least 1 unique element
return "Yes"
# Driver Code
if __name__ == '__main__':
# Given array arr[]
arr = [ 1, 2, 1 ]
N = len(arr)
# Function Call
print(check(arr, N))
# This code is contributed by mohit kumar 29
C#
// C# program for the
// above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to check if all
// subarrays have at least
// one unique element
static String check(int []arr,
int n)
{
// Generate all subarray
for (int i = 0; i < n; i++)
{
// Store frequency of
// subarray's elements
Dictionary<int,
int> hm =
new Dictionary<int,
int>();
int count = 0;
// Traverse the array over
// the range [i, N]
for (int j = i; j < n; j++)
{
// Update frequency of
// current subarray in map
if(hm.ContainsKey((arr[j])))
hm[arr[j]]++;
else
hm.Add(arr[j], 1);
// Increment count
if (hm[arr[j]] == 1)
count++;
// Decrement count
if (hm[arr[j]] == 2)
count--;
if (count == 0)
return "No";
}
}
// If all subarrays have at
// least 1 unique element
return "Yes";
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int[] arr = {1, 2, 1};
int N = arr.Length;
// Function Call
Console.WriteLine(check(arr, N));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
//Javascript program for the above approach
// Function to check if all subarrays
// have at least one unique element
function check(arr, n)
{
// Generate all subarray
for(var i = 0; i < n; i++)
{
// Store frequency of
// subarray's elements
//map<int, int> hm;
var hm= new Map();
var count = 0;
// Traverse the array over
// the range [i, N]
for(var j = i; j < n; j++)
{
// Update frequency of
// current subarray in map
//hm[arr[j]]++;
if(hm.has(arr[j]))
hm.set(arr[j], hm.get(arr[j])+1)
else
hm.set(arr[j], 1)
// Increment count
if (hm.get(arr[j])==1)
count++;
// Decrement count
if (hm.get(arr[j]) == 2)
count--;
if (count == 0)
return "No";
}
}
// If all subarrays have at
// least 1 unique element
return "Yes";
}
var arr = [ 1, 2, 1 ];
var N = arr.length;
// Function Call
document.write(check(arr, N));
// This code is contributed by SoumikMondal
</script>
Producción
Yes
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array