Dadas dos arrays: arr1[0..m-1] y arr2[0..n-1]. Encuentra si arr2[] es un subconjunto de arr1[] o no. Ambas arrays no están ordenadas. Se puede suponer que los elementos de ambas arrays son distintos.
Ejemplos:
C++
// C++ program to find whether an array
// is subset of another array
#include <bits/stdc++.h>
/* Return 1 if arr2[] is a subset of
arr1[] */
bool isSubset(int arr1[], int arr2[],
int m, int n)
{
int i = 0;
int j = 0;
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
if (arr2[i] == arr1[j])
break;
}
/* If the above inner loop was
not broken at all then arr2[i]
is not present in arr1[] */
if (j == m)
return 0;
}
/* If we reach here then all
elements of arr2[] are present
in arr1[] */
return 1;
}
// Driver code
int main()
{
int arr1[] = { 11, 1, 13, 21, 3, 7 };
int arr2[] = { 11, 3, 7, 1 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
if (isSubset(arr1, arr2, m, n))
printf("arr2[] is subset of arr1[] ");
else
printf("arr2[] is not a subset of arr1[]");
getchar();
return 0;
}
Java
// Java program to find whether an array
// is subset of another array
class GFG {
/* Return true if arr2[] is a subset
of arr1[] */
static boolean isSubset(int arr1[],
int arr2[],
int m, int n)
{
int i = 0;
int j = 0;
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++)
if (arr2[i] == arr1[j])
break;
/* If the above inner loop
was not broken at all then
arr2[i] is not present in
arr1[] */
if (j == m)
return false;
}
/* If we reach here then all
elements of arr2[] are present
in arr1[] */
return true;
}
// Driver code
public static void main(String args[])
{
int arr1[] = { 11, 1, 13, 21, 3, 7 };
int arr2[] = { 11, 3, 7, 1 };
int m = arr1.length;
int n = arr2.length;
if (isSubset(arr1, arr2, m, n))
System.out.print("arr2[] is "
+ "subset of arr1[] ");
else
System.out.print("arr2[] is "
+ "not a subset of arr1[]");
}
}
Python3
# Python 3 program to find whether an array
# is subset of another array
# Return 1 if arr2[] is a subset of
# arr1[]
def isSubset(arr1, arr2, m, n):
i = 0
j = 0
for i in range(n):
for j in range(m):
if(arr2[i] == arr1[j]):
break
# If the above inner loop was
# not broken at all then arr2[i]
# is not present in arr1[]
if (j == m):
return 0
# If we reach here then all
# elements of arr2[] are present
# in arr1[]
return 1
# Driver code
if __name__ == "__main__":
arr1 = [11, 1, 13, 21, 3, 7]
arr2 = [11, 3, 7, 1]
m = len(arr1)
n = len(arr2)
if(isSubset(arr1, arr2, m, n)):
print("arr2[] is subset of arr1[] ")
else:
print("arr2[] is not a subset of arr1[]")
# This code is contributed by ita_c
C#
// C# program to find whether an array
// is subset of another array
using System;
class GFG {
/* Return true if arr2[] is a
subset of arr1[] */
static bool isSubset(int[] arr1,
int[] arr2,
int m, int n)
{
int i = 0;
int j = 0;
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++)
if (arr2[i] == arr1[j])
break;
/* If the above inner loop
was not broken at all then
arr2[i] is not present in
arr1[] */
if (j == m)
return false;
}
/* If we reach here then all
elements of arr2[] are present
in arr1[] */
return true;
}
// Driver function
public static void Main()
{
int[] arr1 = { 11, 1, 13, 21, 3, 7 };
int[] arr2 = { 11, 3, 7, 1 };
int m = arr1.Length;
int n = arr2.Length;
if (isSubset(arr1, arr2, m, n))
Console.WriteLine("arr2[] is subset"
+ " of arr1[] ");
else
Console.WriteLine("arr2[] is not a "
+ "subset of arr1[]");
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to find whether an array
// is subset of another array
/* Return 1 if arr2[] is a subset of
arr1[] */
function isSubset($arr1, $arr2, $m, $n)
{
$i = 0;
$j = 0;
for ($i = 0; $i < $n; $i++)
{
for ($j = 0; $j < $m; $j++)
{
if($arr2[$i] == $arr1[$j])
break;
}
/* If the above inner loop was
not broken at all then arr2[i]
is not present in arr1[] */
if ($j == $m)
return 0;
}
/* If we reach here then all
elements of arr2[] are present
in arr1[] */
return 1;
}
// Driver code
$arr1 = array(11, 1, 13, 21, 3, 7);
$arr2 = array(11, 3, 7, 1);
$m = count($arr1);
$n = count($arr2);
if(isSubset($arr1, $arr2, $m, $n))
echo "arr2[] is subset of arr1[] ";
else
echo "arr2[] is not a subset of arr1[]";
// This code is contributed by anuj_67.
?>
Javascript
<script>
// JavaScript program to find whether an array
// is subset of another array
/* Return true if arr2[] is a subset
of arr1[] */
function isSubset(arr1, arr2, m, n)
{
let i = 0;
let j = 0;
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++)
if (arr2[i] == arr1[j])
break;
/* If the above inner loop
was not broken at all then
arr2[i] is not present in
arr1[] */
if (j == m)
return false;
}
/* If we reach here then all
elements of arr2[] are present
in arr1[] */
return true;
}
// Driver Code
let arr1 = [ 11, 1, 13, 21, 3, 7 ];
let arr2 = [ 11, 3, 7, 1 ];
let m = arr1.length;
let n = arr2.length;
if (isSubset(arr1, arr2, m, n))
document.write("arr2[] is "
+ "subset of arr1[] ");
else
document.write("arr2[] is "
+ "not a subset of arr1[]");
</script>
C++
// C++ program to find whether an array
// is subset of another array
#include <bits/stdc++.h>
using namespace std;
/* Function prototypes */
void quickSort(int* arr, int si, int ei);
int binarySearch(int arr[], int low,
int high, int x);
/* Return 1 if arr2[] is a subset of arr1[] */
bool isSubset(int arr1[], int arr2[],
int m, int n)
{
int i = 0;
quickSort(arr1, 0, m - 1);
for (i = 0; i < n; i++) {
if (binarySearch(arr1, 0, m - 1,
arr2[i])
== -1)
return 0;
}
/* If we reach here then all elements
of arr2[] are present in arr1[] */
return 1;
}
/* FOLLOWING FUNCTIONS ARE ONLY FOR
SEARCHING AND SORTING PURPOSE */
/* Standard Binary Search function*/
int binarySearch(int arr[], int low,
int high, int x)
{
if (high >= low)
{
/*low + (high - low)/2;*/
int mid = (low + high) / 2;
/* Check if arr[mid] is the first
occurrence of x. arr[mid] is first
occurrence if x is one of the following
is true:
(i) mid == 0 and arr[mid] == x
(ii) arr[mid-1] < x and arr[mid] == x */
if ((mid == 0 || x > arr[mid - 1]) && (arr[mid] == x))
return mid;
else if (x > arr[mid])
return binarySearch(arr, (mid + 1), high, x);
else
return binarySearch(arr, low, (mid - 1), x);
}
return -1;
}
void exchange(int* a, int* b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int partition(int A[], int si, int ei)
{
int x = A[ei];
int i = (si - 1);
int j;
for (j = si; j <= ei - 1; j++) {
if (A[j] <= x) {
i++;
exchange(&A[i], &A[j]);
}
}
exchange(&A[i + 1], &A[ei]);
return (i + 1);
}
/* Implementation of Quick Sort
A[] --> Array to be sorted
si --> Starting index
ei --> Ending index
*/
void quickSort(int A[], int si, int ei)
{
int pi; /* Partitioning index */
if (si < ei) {
pi = partition(A, si, ei);
quickSort(A, si, pi - 1);
quickSort(A, pi + 1, ei);
}
}
/*Driver code */
int main()
{
int arr1[] = { 11, 1, 13, 21, 3, 7 };
int arr2[] = { 11, 3, 7, 1 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
if (isSubset(arr1, arr2, m, n))
cout << "arr2[] is subset of arr1[] ";
else
cout << "arr2[] is not a subset of arr1[] ";
return 0;
}
// This code is contributed by Shivi_Aggarwal
C
// C program to find whether an array
// is subset of another array
#include <stdbool.h>
#include <stdio.h>
/* Function prototypes */
void quickSort(int* arr, int si, int ei);
int binarySearch(int arr[], int low,
int high, int x);
/* Return 1 if arr2[] is a subset of arr1[] */
bool isSubset(int arr1[], int arr2[],
int m, int n)
{
int i = 0;
quickSort(arr1, 0, m - 1);
for (i = 0; i < n; i++) {
if (binarySearch(arr1, 0, m - 1,
arr2[i]) == -1)
return 0;
}
/* If we reach here then all elements of arr2[]
are present in arr1[] */
return 1;
}
/* FOLLOWING FUNCTIONS ARE ONLY FOR SEARCHING
AND SORTING PURPOSE */
/* Standard Binary Search function*/
int binarySearch(int arr[], int low, int high, int x)
{
if (high >= low)
{
/*low + (high - low)/2;*/
int mid = (low + high) / 2;
/* Check if arr[mid] is the first
occurrence of x.
arr[mid] is first occurrence if x is
one of the following
is true:
(i) mid == 0 and arr[mid] == x
(ii) arr[mid-1] < x and arr[mid] == x
*/
if ((mid == 0 || x > arr[mid - 1]) && (arr[mid] == x))
return mid;
else if (x > arr[mid])
return binarySearch(arr, (mid + 1), high, x);
else
return binarySearch(arr, low, (mid - 1), x);
}
return -1;
}
void exchange(int* a, int* b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int partition(int A[], int si, int ei)
{
int x = A[ei];
int i = (si - 1);
int j;
for (j = si; j <= ei - 1; j++) {
if (A[j] <= x) {
i++;
exchange(&A[i], &A[j]);
}
}
exchange(&A[i + 1], &A[ei]);
return (i + 1);
}
/* Implementation of Quick Sort
A[] --> Array to be sorted
si --> Starting index
ei --> Ending index
*/
void quickSort(int A[], int si, int ei)
{
int pi; /* Partitioning index */
if (si < ei) {
pi = partition(A, si, ei);
quickSort(A, si, pi - 1);
quickSort(A, pi + 1, ei);
}
}
/*Driver code */
int main()
{
int arr1[] = { 11, 1, 13, 21, 3, 7 };
int arr2[] = { 11, 3, 7, 1 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
if (isSubset(arr1, arr2, m, n))
printf("arr2[] is subset of arr1[] ");
else
printf("arr2[] is not a subset of arr1[] ");
return 0;
}
Java
// Java program to find whether an array
// is subset of another array
class Main {
/* Return true if arr2[] is a subset of arr1[] */
static boolean isSubset(int arr1[],
int arr2[], int m,
int n)
{
int i = 0;
sort(arr1, 0, m - 1);
for (i = 0; i < n; i++) {
if (binarySearch(arr1,
0, m - 1,
arr2[i]) == -1)
return false;
}
/* If we reach here then all elements of arr2[]
are present in arr1[] */
return true;
}
/* FOLLOWING FUNCTIONS ARE ONLY
FOR SEARCHING AND
* SORTING PURPOSE */
/* Standard Binary Search function*/
static int binarySearch(int arr[],
int low, int high,
int x)
{
if (high >= low)
{
/*low + (high - low)/2;*/
int mid = (low + high)
/ 2;
/* Check if arr[mid] is the first occurrence of
x. arr[mid] is first occurrence if x is one of
the following is true: (i) mid == 0 and
arr[mid] == x (ii) arr[mid-1] < x and arr[mid]
== x
*/
if ((mid == 0 || x > arr[mid - 1])
&& (arr[mid] == x))
return mid;
else if (x > arr[mid])
return binarySearch(arr,
(mid + 1), high,
x);
else
return binarySearch(arr, low,
(mid - 1), x);
}
return -1;
}
/* This function takes last element as pivot,
places the pivot element at its correct
position in sorted array, and places all
smaller (smaller than pivot) to left of
pivot and all greater elements to right
of pivot */
static int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
/* The main function that implements QuickSort()
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
static void sort(int arr[], int low, int high)
{
if (low < high) {
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
sort(arr, low, pi - 1);
sort(arr, pi + 1, high);
}
}
// Driver Code
public static void main(String args[])
{
int arr1[] = { 11, 1, 13, 21, 3, 7 };
int arr2[] = { 11, 3, 7, 1 };
int m = arr1.length;
int n = arr2.length;
if (isSubset(arr1, arr2, m, n))
System.out.print("arr2[] is subset of arr1[] ");
else
System.out.print(
"arr2[] is not a subset of arr1[]");
}
}
Python3
# Python3 program to find whether an array
# is subset of another array
# Return 1 if arr2[] is a subset of arr1[]
def isSubset(arr1, arr2, m, n):
i = 0
quickSort(arr1, 0, m-1)
for i in range(n):
if (binarySearch(arr1, 0, m - 1, arr2[i]) == -1):
return 0
# If we reach here then all elements
# of arr2[] are present in arr1[]
return 1
# FOLLOWING FUNCTIONS ARE ONLY FOR
# SEARCHING AND SORTING PURPOSE
# Standard Binary Search function
def binarySearch(arr, low, high, x):
if(high >= low):
mid = (low + high)//2
# Check if arr[mid] is the first
# occurrence of x.
# arr[mid] is first occurrence if x is
# one of the following
# is true:
# (i) mid == 0 and arr[mid] == x
# (ii) arr[mid-1] < x and arr[mid] == x
if((mid == 0 or x > arr[mid-1]) and (arr[mid] == x)):
return mid
elif(x > arr[mid]):
return binarySearch(arr, (mid + 1), high, x)
else:
return binarySearch(arr, low, (mid - 1), x)
return -1
def partition(A, si, ei):
x = A[ei]
i = (si - 1)
for j in range(si, ei):
if(A[j] <= x):
i += 1
A[i], A[j] = A[j], A[i]
A[i + 1], A[ei] = A[ei], A[i + 1]
return (i + 1)
# Implementation of Quick Sort
# A[] --> Array to be sorted
# si --> Starting index
# ei --> Ending index
def quickSort(A, si, ei):
# Partitioning index
if(si < ei):
pi = partition(A, si, ei)
quickSort(A, si, pi - 1)
quickSort(A, pi + 1, ei)
# Driver code
arr1 = [11, 1, 13, 21, 3, 7]
arr2 = [11, 3, 7, 1]
m = len(arr1)
n = len(arr2)
if(isSubset(arr1, arr2, m, n)):
print("arr2[] is subset of arr1[] ")
else:
print("arr2[] is not a subset of arr1[] ")
# This code is contributed by chandan_jnu
C#
// C# program to find whether an array
// is subset of another array
using System;
public class GFG {
/* Return true if arr2[] is a subset of arr1[] */
static bool isSubset(int[] arr1,
int[] arr2,
int m, int n)
{
int i = 0;
sort(arr1, 0, m - 1);
for (i = 0; i < n; i++)
{
if (binarySearch(arr1, 0, m - 1, arr2[i]) == -1)
return false;
}
/* If we reach here then all elements of arr2[]
are present in arr1[] */
return true;
}
/* FOLLOWING FUNCTIONS ARE ONLY FOR SEARCHING AND SORTING PURPOSE */
/* Standard Binary Search function*/
static int binarySearch(int[] arr,
int low,
int high, int x)
{
if (high >= low)
{
int mid = (low + high) / 2;
/* Check if arr[mid] is the first
occurrence of x.
arr[mid] is first occurrence if x
is one of the following
is true:
(i) mid == 0 and arr[mid] == x
(ii) arr[mid-1] < x and arr[mid] == x
*/
if ((mid == 0 || x > arr[mid - 1])
&& (arr[mid] == x))
return mid;
else if (x > arr[mid])
return binarySearch(arr,
(mid + 1), high, x);
else
return binarySearch(arr,
low, (mid - 1), x);
}
return -1;
}
/* This function takes last element as pivot,
places the pivot element at its correct
position in sorted array, and places all
smaller (smaller than pivot) to left of
pivot and all greater elements to right
of pivot */
static int partition(int[] arr, int low, int high)
{
int pivot = arr[high];
int i = (low - 1);
int temp = 0;
for (int j = low; j < high; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++;
// swap arr[i] and arr[j]
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
/* The main function that implements QuickSort()
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
static void sort(int[] arr, int low, int high)
{
if (low < high) {
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
sort(arr, low, pi - 1);
sort(arr, pi + 1, high);
}
}
// Driver Code
public static void Main()
{
int[] arr1 = { 11, 1, 13, 21, 3, 7 };
int[] arr2 = { 11, 3, 7, 1 };
int m = arr1.Length;
int n = arr2.Length;
if (isSubset(arr1, arr2, m, n))
Console.Write("arr2[] is subset of arr1[] ");
else
Console.Write("arr2[] is not a subset of arr1[]");
}
}
// This code is contributed by 29AjayKumar
PHP
<?php
// PHP program to find whether an array
// is subset of another array
/* Return 1 if arr2[] is a subset of arr1[] */
function isSubset($arr1, $arr2,
$m, $n)
{
$i = 0;
quickSort($arr1, 0, $m-1);
for ($i = 0; $i < $n; $i++)
{
if (binarySearch($arr1, 0, $m - 1,
$arr2[$i]) == -1)
return 0;
}
/* If we reach here then all elements
of arr2[] are present in arr1[] */
return 1;
}
/* FOLLOWING FUNCTIONS ARE ONLY FOR
SEARCHING AND SORTING PURPOSE */
/* Standard Binary Search function*/
function binarySearch($arr, $low, $high, $x)
{
if($high >= $low)
{
$mid = (int)(($low + $high)/2);
/* Check if arr[mid] is the first
occurrence of x.
arr[mid] is first occurrence if
x is one of the following
is true:
(i) mid == 0 and arr[mid] == x
(ii) arr[mid-1] < x and arr[mid] == x */
if(( $mid == 0 || $x > $arr[$mid-1])
&& ($arr[$mid] == $x))
return $mid;
else if($x > $arr[$mid])
return binarySearch($arr,
($mid + 1), $high, $x);
else
return binarySearch($arr,
$low, ($mid -1), $x);
}
return -1;
}
function exchange(&$a, &$b)
{
$temp = $a;
$a = $b;
$b = $temp;
}
function partition(&$A, $si, $ei)
{
$x = $A[$ei];
$i = ($si - 1);
for ($j = $si; $j <= $ei - 1; $j++)
{
if($A[$j] <= $x)
{
$i++;
exchange($A[$i], $A[$j]);
}
}
exchange ($A[$i + 1], $A[$ei]);
return ($i + 1);
}
/* Implementation of Quick Sort
A[] --> Array to be sorted
si --> Starting index
ei --> Ending index
*/
function quickSort(&$A, $si, $ei)
{
/* Partitioning index */
if($si < $ei)
{
$pi = partition($A, $si, $ei);
quickSort($A, $si, $pi - 1);
quickSort($A, $pi + 1, $ei);
}
}
/*Driver code */
$arr1 = array(11, 1, 13, 21, 3, 7);
$arr2 = array(11, 3, 7, 1);
$m = count($arr1);
$n = count($arr2);
if(isSubset($arr1, $arr2, $m, $n))
echo "arr2[] is subset of arr1[] ";
else
echo "arr2[] is not a subset of arr1[] ";
// This code is contributed by chandan_jnu
?>
Javascript
<script>
// Javascript program to find whether an array
// is subset of another array
// Return true if arr2[] is a subset of arr1[]
function isSubset(arr1, arr2, m, n)
{
let i = 0;
sort(arr1, 0, m - 1);
for(i = 0; i < n; i++)
{
if (binarySearch(arr1, 0, m - 1,
arr2[i]) == -1)
return false;
}
// If we reach here then all elements
// of arr2[] are present in arr1[]
return true;
}
/* FOLLOWING FUNCTIONS ARE ONLY
FOR SEARCHING AND
* SORTING PURPOSE */
/* Standard Binary Search function*/
function binarySearch(arr, low, high, x)
{
if (high >= low)
{
// low + (high - low)/2;
let mid = Math.floor((low + high) / 2);
// Check if arr[mid] is the first occurrence of
// x. arr[mid] is first occurrence if x is one of
// the following is true: (i) mid == 0 and
// arr[mid] == x (ii) arr[mid-1] < x and arr[mid] == x
if ((mid == 0 || x > arr[mid - 1]) &&
(arr[mid] == x))
return mid;
else if (x > arr[mid])
return binarySearch(arr, (mid + 1),
high, x);
else
return binarySearch(arr, low,
(mid - 1), x);
}
return -1;
}
/* This function takes last element as pivot,
places the pivot element at its correct
position in sorted array, and places all
smaller (smaller than pivot) to left of
pivot and all greater elements to right
of pivot */
function partition(arr, low, high)
{
let pivot = arr[high];
let i = (low - 1);
for(let j = low; j < high; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++;
// Swap arr[i] and arr[j]
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swap arr[i+1] and arr[high] (or pivot)
let temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
/* The main function that implements QuickSort()
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
function sort(arr,low,high)
{
if (low < high)
{
// pi is partitioning index, arr[pi]
// is now at right place
let pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
sort(arr, low, pi - 1);
sort(arr, pi + 1, high);
}
}
// Driver Code
let arr1 = [ 11, 1, 13, 21, 3, 7 ];
let arr2 = [ 11, 3, 7, 1 ];
let m = arr1.length;
let n = arr2.length;
if (isSubset(arr1, arr2, m, n))
document.write("arr2[] is subset of arr1[] ");
else
document.write("arr2[] is not a subset of arr1[]");
// This code is contributed by patel2127
</script>
C++
// C++ program to find whether an array
// is subset of another array
#include <bits/stdc++.h>
using namespace std;
/* Return 1 if arr2[] is a subset of arr1[] */
bool isSubset(int arr1[], int arr2[],
int m, int n)
{
int i = 0, j = 0;
if (m < n)
return 0;
// Sort both the arrays
sort(arr1, arr1 + m);
sort(arr2, arr2 + n);
// Iterate till they do not exceed their sizes
while (i < n && j < m)
{
// If the element is smaller then
// Move ahead in the first array
if (arr1[j] < arr2[i])
j++;
// If both are equal, then move
// both of them forward
else if (arr1[j] == arr2[i])
{
j++;
i++;
}
// If we do not have an element smaller
// or equal to the second array then break
else if (arr1[j] > arr2[i])
return 0;
}
return (i < n) ? false : true;
}
// Driver Code
int main()
{
int arr1[] = { 11, 1, 13, 21, 3, 7 };
int arr2[] = { 11, 3, 7, 1 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
if (isSubset(arr1, arr2, m, n))
printf("arr2[] is subset of arr1[] ");
else
printf("arr2[] is not a subset of arr1[] ");
return 0;
}
Java
// Java code to find whether an array is subset of
// another array
import java.util.Arrays;
class GFG
{
/* Return true if arr2[] is a subset of arr1[] */
static boolean isSubset(int arr1[],
int arr2[], int m,
int n)
{
int i = 0, j = 0;
if (m < n)
return false;
Arrays.sort(arr1); // sorts arr1
Arrays.sort(arr2); // sorts arr2
while (i < n && j < m) {
if (arr1[j] < arr2[i])
j++;
else if (arr1[j] == arr2[i]) {
j++;
i++;
}
else if (arr1[j] > arr2[i])
return false;
}
if (i < n)
return false;
else
return true;
}
// Driver Code
public static void main(String[] args)
{
int arr1[] = { 11, 1, 13, 21, 3, 7 };
int arr2[] = { 11, 3, 7, 1 };
int m = arr1.length;
int n = arr2.length;
if (isSubset(arr1, arr2, m, n))
System.out.println("arr2 is a subset of arr1");
else
System.out.println("arr2 is not a subset of arr1");
}
}
// This code is contributed by Kamal Rawal
Python3
# Python3 program to find whether an array
# is subset of another array
# Return 1 if arr2[] is a subset of arr1[] */
def isSubset(arr1, arr2, m, n):
i = 0
j = 0
if m < n:
return 0
arr1.sort()
arr2.sort()
while i < n and j < m:
if arr1[j] < arr2[i]:
j += 1
elif arr1[j] == arr2[i]:
j += 1
i += 1
elif arr1[j] > arr2[i]:
return 0
return False if i < n else True
# Driver code
arr1 = [11, 1, 13, 21, 3, 7]
arr2 = [11, 3, 7, 1]
m = len(arr1)
n = len(arr2)
if isSubset(arr1, arr2, m, n) == True:
print("arr2 is subset of arr1 ")
else:
printf("arr2 is not a subset of arr1 ")
# This code is contributed by Shrikant13
C#
// C# code to find whether an array
// is subset of another array
using System;
class GFG {
// Return true if arr2[] is
// a subset of arr1[] */
static bool isSubset(int[] arr1,
int[] arr2, int m,
int n)
{
int i = 0, j = 0;
if (m < n)
return false;
// sorts arr1
Array.Sort(arr1);
// sorts arr2
Array.Sort(arr2);
while (i < n && j < m)
{
if (arr1[j] < arr2[i])
j++;
else if (arr1[j] == arr2[i])
{
j++;
i++;
}
else if (arr1[j] > arr2[i])
return false;
}
if (i < n)
return false;
else
return true;
}
// Driver Code
public static void Main()
{
int[] arr1 = { 11, 1, 13, 21, 3, 7 };
int[] arr2 = { 11, 3, 7, 1 };
int m = arr1.Length;
int n = arr2.Length;
if (isSubset(arr1, arr2, m, n))
Console.Write("arr2 is a subset of arr1");
else
Console.Write("arr2 is not a subset of arr1");
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to find whether an array
// is subset of another array
/* Return 1 if arr2[] is a subset of arr1[] */
function isSubset( $arr1, $arr2, $m, $n)
{
$i = 0; $j = 0;
if ($m < $n)
return 0;
sort($arr1);
sort($arr2);
while ($i < $n and $j < $m )
{
if( $arr1[$j] <$arr2[$i] )
$j++;
else if( $arr1[$j] == $arr2[$i] )
{
$j++;
$i++;
}
else if( $arr1[$j] > $arr2[$i] )
return 0;
}
return ($i < $n) ? false : true;
}
/*Driver code */
$arr1 = array(11, 1, 13, 21, 3, 7);
$arr2 = array(11, 3, 7, 1);
$m = count($arr1);
$n = count($arr2);
if(isSubset($arr1, $arr2, $m, $n))
echo "arr2[] is subset of arr1[] ";
else
echo "arr2[] is not a subset of arr1[] ";
// This code is contributed by anuj_67.
?>
Javascript
<script>
// JavaScript program to find whether an array
// is subset of another array
// Return 1 if arr2[] is a subset of arr1[]
function isSubset(arr1, arr2, m, n)
{
let i = 0, j = 0;
if (m < n)
return 0;
// Sort both the arrays
arr1.sort((a, b) => a - b);
arr2.sort((a, b) => a - b);
// Iterate till they do not exceed their sizes
while (i < n && j < m)
{
// If the element is smaller then
// Move ahead in the first array
if (arr1[j] < arr2[i])
j++;
// If both are equal, then move
// both of them forward
else if (arr1[j] == arr2[i])
{
j++;
i++;
}
// If we do not have an element smaller
// or equal to the second array then break
else if (arr1[j] > arr2[i])
return 0;
}
return (i < n) ? false : true;
}
// Driver Code
let arr1 = [ 11, 1, 13, 21, 3, 7 ];
let arr2 = [ 11, 3, 7, 1 ];
let m = arr1.length;
let n = arr2.length;
if (isSubset(arr1, arr2, m, n))
document.write("arr2[] is subset of arr1[] ");
else
document.write("arr2[] is not a subset of arr1[] ");
// This code is contributed by Manoj.
</script>
C++
// C++ code to find whether an array is subset of
// another array
#include <bits/stdc++.h>
using namespace std;
/* Return true if arr2[] is a subset of arr1[] */
bool isSubset(int arr1[], int m,
int arr2[], int n)
{
// Using STL set for hashing
set<int> hashset;
// hset stores all the values of arr1
for (int i = 0; i < m; i++)
{
hashset.insert(arr1[i]);
}
// loop to check if all elements of arr2 also
// lies in arr1
for (int i = 0; i < n; i++) {
if (hashset.find(arr2[i]) == hashset.end())
return false;
}
return true;
}
// Driver Code
int main()
{
int arr1[] = { 11, 1, 13, 21, 3, 7 };
int arr2[] = { 11, 3, 7, 1 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
if (isSubset(arr1, m, arr2, n))
cout << "arr2[] is subset of arr1[] "
<< "\n";
else
cout << "arr2[] is not a subset of arr1[] "
<< "\n";
return 0;
}
// This code is contributed by Satvik Shrivas
Java
// Java code to find whether an array is subset of
// another array
import java.util.HashSet;
class GFG
{
/* Return true if arr2[] is a subset of arr1[] */
static boolean isSubset(int arr1[],
int arr2[], int m,
int n)
{
HashSet<Integer> hset = new HashSet<>();
// hset stores all the values of arr1
for (int i = 0; i < m; i++) {
if (!hset.contains(arr1[i]))
hset.add(arr1[i]);
}
// loop to check if all elements
// of arr2 also lies in arr1
for (int i = 0; i < n; i++)
{
if (!hset.contains(arr2[i]))
return false;
}
return true;
}
// Driver Code
public static void main(String[] args)
{
int arr1[] = { 11, 1, 13, 21, 3, 7 };
int arr2[] = { 11, 3, 7, 1 };
int m = arr1.length;
int n = arr2.length;
if (isSubset(arr1, arr2, m, n))
System.out.println("arr2 is a subset of arr1");
else
System.out.println(
"arr2 is not a subset of arr1");
}
}
// This code is contributed by Kamal Rawal
Python3
# Python3 program to find whether an array
# is subset of another array
# Return true if arr2[] is a subset
# of arr1[]
def isSubset(arr1, m, arr2, n):
# Using STL set for hashing
hashset = set()
# hset stores all the values of arr1
for i in range(0, m):
hashset.add(arr1[i])
# Loop to check if all elements
# of arr2 also lies in arr1
for i in range(0, n):
if arr2[i] in hashset:
continue
else:
return False
return True
# Driver Code
if __name__ == '__main__':
arr1 = [ 11, 1, 13, 21, 3, 7 ]
arr2 = [ 11, 3, 7, 1 ]
m = len(arr1)
n = len(arr2)
if (isSubset(arr1, m, arr2, n)):
print("arr2[] is subset of arr1[] ")
else:
print("arr2[] is not a subset of arr1[] ")
# This code is contributed by akhilsaini
C#
// C# code to find whether an array is
// subset of another array
using System;
using System.Collections.Generic;
class GFG {
/* Return true if arr2[] is a
subset of arr1[] */
public static bool isSubset(int[] arr1,
int[] arr2,
int m, int n)
{
HashSet<int> hset = new HashSet<int>();
// hset stores all the values of arr1
for (int i = 0; i < m; i++)
{
if (!hset.Contains(arr1[i]))
{
hset.Add(arr1[i]);
}
}
// loop to check if all elements
// of arr2 also lies in arr1
for (int i = 0; i < n; i++)
{
if (!hset.Contains(arr2[i]))
{
return false;
}
}
return true;
}
// Driver Code
public static void Main(string[] args)
{
int[] arr1 = new int[] { 11, 1, 13, 21, 3, 7 };
int[] arr2 = new int[] { 11, 3, 7, 1 };
int m = arr1.Length;
int n = arr2.Length;
if (isSubset(arr1, arr2, m, n)) {
Console.WriteLine("arr2 is a subset of arr1");
}
else {
Console.WriteLine(
"arr2 is not a subset of arr1");
}
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Javascript code to find whether an
// array is subset of another array
// Return true if arr2[] is a
// subset of arr1[]
function isSubset(arr1, arr2, m, n)
{
let hset = new Set();
// hset stores all the values of arr1
for(let i = 0; i < m; i++)
{
if (!hset.has(arr1[i]))
hset.add(arr1[i]);
}
// Loop to check if all elements
// of arr2 also lies in arr1
for(let i = 0; i < n; i++)
{
if (!hset.has(arr2[i]))
return false;
}
return true;
}
// Driver Code
let arr1 = [ 11, 1, 13, 21, 3, 7 ];
let arr2 = [ 11, 3, 7, 1 ];
let m = arr1.length;
let n = arr2.length;
if (isSubset(arr1, arr2, m, n))
document.write("arr2 is a subset of arr1");
else
document.write("arr2 is not a subset of arr1");
// This code is contributed by unknown2108
</script>
C++
#include <bits/stdc++.h>
using namespace std;
int main()
{
// code
int arr1[] = { 11, 1, 13, 21, 3, 7 };
int arr2[] = { 11, 3, 7, 1 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
unordered_set<int> s;
for (int i = 0; i < m; i++) {
s.insert(arr1[i]);
}
int p = s.size();
for (int i = 0; i < n; i++) {
s.insert(arr2[i]);
}
if (s.size() == p) {
cout << "arr2[] is subset of arr1[] "
<< "\n";
}
else {
cout << "arr2[] is not subset of arr1[] "
<< "\n";
}
return 0;
}
Java
import java.io.*;
import java.util.*;
class GFG
{
public static void main (String[] args)
{
int arr1[] = { 11, 1, 13, 21, 3, 7 };
int arr2[] = { 11, 3, 7, 1 };
int m=arr1.length;
int n=arr2.length;
Set<Integer> s = new HashSet<Integer>();
for (int i = 0; i < m; i++)
{
s.add(arr1[i]);
}
int p = s.size();
for (int i = 0; i < n; i++)
{
s.add(arr2[i]);
}
if (s.size() == p)
{
System.out.println("arr2[] is subset of arr1[] " + "\n");
}
else
{
System.out.println("arr2[] is not subset of arr1[] " + "\n" );
}
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 code
arr1 = [ 11, 1, 13, 21, 3, 7 ]
arr2 = [ 11, 3, 7, 1 ]
m = len(arr1)
n = len(arr2)
s = set()
for i in range(m) :
s.add(arr1[i])
p = len(s)
for i in range(n) :
s.add(arr2[i])
if (len(s) == p) :
print("arr2[] is subset of arr1[] ")
else :
print("arr2[] is not subset of arr1[] ")
# This code is contributed by divyeshrabadiya07.
C#
using System;
using System.Collections.Generic;
public class GFG
{
static public void Main ()
{
int[] arr1 = { 11, 1, 13, 21, 3, 7 };
int[] arr2 = { 11, 3, 7, 1 };
int m = arr1.Length;
int n = arr2.Length;
HashSet<int> s = new HashSet<int>();
for (int i = 0; i < m; i++)
{
s.Add(arr1[i]);
}
int p = s.Count;
for (int i = 0; i < n; i++)
{
s.Add(arr2[i]);
}
if (s.Count == p)
{
Console.WriteLine("arr2[] is subset of arr1[] " + "\n");
}
else
{
Console.WriteLine("arr2[] is not subset of arr1[] " + "\n" );
}
}
}
// This code is contributed by rag2127
Javascript
<script>
let arr1=[11, 1, 13, 21, 3, 7];
let arr2=[11, 3, 7, 1 ];
let m=arr1.length;
let n=arr2.length;
let s = new Set();
for (let i = 0; i < m; i++)
{
s.add(arr1[i]);
}
let p = s.size;
for (let i = 0; i < n; i++)
{
s.add(arr2[i]);
}
if (s.size == p)
{
document.write("arr2[] is subset of arr1[] " + "<br>");
}
else
{
document.write("arr2[] is not subset of arr1[] " + "<br>" );
}
// This code is contributed by ab2127
</script>
C++14
// C++ program to find whether an array
// is subset of another array
#include <bits/stdc++.h>
using namespace std;
/* Return true if arr2[] is a subset of arr1[] */
bool isSubset(int arr1[], int m,
int arr2[], int n)
{
// Create a Frequency Table using STL
map<int, int> frequency;
// Increase the frequency of each element
// in the frequency table.
for (int i = 0; i < m; i++)
{
frequency[arr1[i]]++;
}
// Decrease the frequency if the
// element was found in the frequency
// table with the frequency more than 0.
// else return 0 and if loop is
// completed return 1.
for (int i = 0; i < n; i++)
{
if (frequency[arr2[i]] > 0)
frequency[arr2[i]]--;
else
{
return false;
}
}
return true;
}
// Driver Code
int main()
{
int arr1[] = { 11, 1, 13, 21, 3, 7 };
int arr2[] = { 11, 3, 7, 1 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
if (isSubset(arr1, m, arr2, n))
cout << "arr2[] is subset of arr1[] "
<< "\n";
else
cout << "arr2[] is not a subset of arr1[] "
<< "\n";
return 0;
}
// This code is contributed by Dhawal Sarin.
Java
// Java program to find whether an array
// is subset of another array
import java.io.*;
import java.util.*;
class GFG{
// Return true if arr2[] is a subset of arr1[]
static boolean isSubset(int[] arr1, int m,
int[] arr2, int n)
{
// Create a Frequency Table using STL
HashMap<Integer,
Integer> frequency = new HashMap<Integer,
Integer>();
// Increase the frequency of each element
// in the frequency table.
for(int i = 0; i < m; i++)
{
frequency.put(arr1[i],
frequency.getOrDefault(
arr1[i], 0) + 1);
}
// Decrease the frequency if the
// element was found in the frequency
// table with the frequency more than 0.
// else return 0 and if loop is
// completed return 1.
for(int i = 0; i < n; i++)
{
if (frequency.getOrDefault(arr2[i], 0) > 0)
frequency.put(arr2[i],
frequency.get(arr1[i]) - 1);
else
{
return false;
}
}
return true;
}
// Driver Code
public static void main(String[] args)
{
int[] arr1 = { 11, 1, 13, 21, 3, 7 };
int[] arr2 = { 11, 3, 7, 1 };
int m = arr1.length;
int n = arr2.length;
if (isSubset(arr1, m, arr2, n))
System.out.println(
"arr2[] is subset of arr1[] ");
else
System.out.println(
"arr2[] is not a subset of arr1[] ");
}
}
// This code is contributed by akhilsaini
Python3
# Python3 program to find whether an array
# is subset of another array
# Return true if arr2[] is a subset of arr1[]
def isSubset(arr1, m, arr2, n):
# Create a Frequency Table using STL
frequency = {}
# Increase the frequency of each element
# in the frequency table.
for i in range(0, m):
if arr1[i] in frequency:
frequency[arr1[i]] = frequency[arr1[i]] + 1
else:
frequency[arr1[i]] = 1
# Decrease the frequency if the
# element was found in the frequency
# table with the frequency more than 0.
# else return 0 and if loop is
# completed return 1.
for i in range(0, n):
if (frequency[arr2[i]] > 0):
frequency[arr2[i]] -= 1
else:
return False
return True
# Driver Code
if __name__ == '__main__':
arr1 = [ 11, 1, 13, 21, 3, 7 ]
arr2 = [ 11, 3, 7, 1 ]
m = len(arr1)
n = len(arr2)
if (isSubset(arr1, m, arr2, n)):
print("arr2[] is subset of arr1[] ")
else:
print("arr2[] is not a subset of arr1[] ")
# This code is contributed by akhilsaini
C#
// C# program to find whether an array
// is subset of another array
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
// Return true if arr2[] is a subset of arr1[]
static bool isSubset(int[] arr1, int m,
int[] arr2, int n)
{
// Create a Frequency Table using STL
Dictionary<int,
int> frequency = new Dictionary<int,
int>();
// Increase the frequency of each element
// in the frequency table.
for(int i = 0; i < m; i++)
{
if (frequency.ContainsKey(arr1[i]))
frequency[arr1[i]] += 1;
else
frequency[arr1[i]] = 1;
}
// Decrease the frequency if the
// element was found in the frequency
// table with the frequency more than 0.
// else return 0 and if loop is
// completed return 1.
for(int i = 0; i < n; i++)
{
if (frequency[arr2[i]] > 0)
frequency[arr2[i]] -= 1;
else
{
return false;
}
}
return true;
}
// Driver Code
public static void Main()
{
int[] arr1 = { 11, 1, 13, 21, 3, 7 };
int[] arr2 = { 11, 3, 7, 1 };
int m = arr1.Length;
int n = arr2.Length;
if (isSubset(arr1, m, arr2, n))
Console.WriteLine(
"arr2[] is subset of arr1[] ");
else
Console.WriteLine(
"arr2[] is not a subset of arr1[] ");
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// javascript program to find whether an array
// is subset of another array
/* Return true if arr2[] is a subset of arr1[] */
function isSubset(arr1,m,arr2,n)
{
// Create a Frequency Table using STL
let frequency = new Array(arr1);
// Increase the frequency of each element
// in the frequency table.
for (let i = 0; i < m; i++)
{
frequency[arr1[i]]++;
}
// Decrease the frequency if the
// element was found in the frequency
// table with the frequency more than 0.
// else return 0 and if loop is
// completed return 1.
for (let i = 0; i < n; i++)
{
if (frequency[arr2[i]] > 0)
frequency[arr2[i]]--;
else
{
return false;
}
}
return true;
}
// Driver Code
let arr1 = [11, 1, 13, 21, 3, 7 ];
let arr2 = [ 11, 3, 7, 1 ];
let m = arr1.length;
let n = arr2.length;
if (isSubset(arr1, m, arr2, n))
document.write("arr2[] is subset of arr1[] "
+ "\n");
else
document.write("arr2[] is not a subset of arr1[] "
+ "\n");
// This code is contributed by vaibhavrabadiya117.
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA