In the previous article, we have seen Java Program to Find the Largest Palindrome in an Array
In this article we are going to see how to check if the given arrays are disjoint using JAVA programming language.
Java Program to Check if the Given Arrays are Disjoint
Array is a data structure which stores a fixed size sequential collection of values of single type. Where with every array elements/values memory location is associated. Each array elements have it’s own index where array index starts from 0.
In Array set of variables referenced by a single variable name and it’s array index position. It is also called as a container object which contains elements of similar type.
Declaration of an array:
dataType[] arrayName; (or) //Declaring an array dataType []arrayName; (or) dataType arr[];
Instantiation of an Array:
arrayName = new datatype[size]; //Allocating memory to array
Combining both Statements in One:
dataType[] arrayName = new dataType[size] //Declaring and Instantiating array
Initialization of an Array:
arrayName[index-0]= arrayElement1 //Initializing the array ... arrayName[index-s]= arrayElementS
Combining all Statements in One:
dataType arrayName[ ]={e1,e2,e3}; //declaration, instantiation and initialization
Disjoint Arrays:
If two or more arrays have some common elements then the arrays are not said to be disjoint arrays. But if the arrays have unique elements in each then those arrays said to be disjoint arrays.
Example:
Case-1
array1={1,2,3,4,5}
array2={4,5,6,7,8,9}
Here both arrays i.e. array1 and array2 are not disjoint as element 4 and 5 are common in both arrays.
Case-2
array3={1,2,3,4,5}
array4={6,7,8,9}
Here both arrays i.e. array3 and array4 are disjoint as both arrays have unique elements.
Let’s see different ways to check if the given arrays are disjoint.
Method-1: By Using two for loops
Approach:
- Run two nested for loops.
- For each element in the first array check its occurrence in the second array.
- If any occurrence is found return false.
- Else return true.
Program:
public class Main
{
public static void main(String[] args)
{
int[] a = { 1, 2, 3, 4, 5 };
int[] b = { 2, 3, 4, 5, 6 };
if (checkDisjoint(a, b))
System.out.println("The given arrays are disjoint.");
else
System.out.println("The given arrays are not disjoint");
}
static boolean checkDisjoint(int[] a, int[] b)
{
for (int i : a)
{
for (int j : b)
{
if (i == j)
return false;
}
}
return true;
}
}
Output: The given arrays are not disjoint
Method-2: By Using Sorting and Binary Search
Approach:
- Create scanner class object.
- Ask use length of the array.
- Initialize the array with given size.
- Ask the user for array elements.
- Iterate over the array.
- Sort first array.
- Iterate through every element of the second array, and use binary search to search every element of the first array in the first array.
- If an element is found, return false
Program:
import java.util.Arrays;
import java.util.Scanner;
public class Main
{
public static void main(String[] args)
{
// create scanner class object
Scanner sc = new Scanner(System.in);
// take input from user for array size
System.out.print("Enter the size 1st of array: ");
int n = sc.nextInt();
// initialize array with size n
int[] a = new int[n];
// take input from user for array elements
System.out.print("Enter array elements: ");
for (int i = 0; i < n; i++)
{
a[i] = sc.nextInt();
}
System.out.print("Enter the size 2nd of array: ");
int m = sc.nextInt();
// initialize array with size n
int[] b = new int[m];
// take input from user for array elements
System.out.print("Enter array elements: ");
for (int i = 0; i < m; i++)
{
b[i] = sc.nextInt();
}
if (checkDisjointBinarySearch(a, b))
System.out.println("The given arrays are disjoint.");
else
System.out.println("The given arrays are not disjoint");
}
static boolean checkDisjointBinarySearch(int[] a, int[] b)
{
Arrays.sort(a);
for (int i : b)
{
if (Arrays.binarySearch(a, i) >= 0)
return false;
}
return true;
}
}
Output: Case-1 Enter the size 1st of array: 4 Enter array elements: 1 2 3 4 Enter the size 2nd of array: 5 Enter array elements: 2 3 4 5 6 The given arrays are not disjoint Case-2 Enter the size 1st of array: 4 Enter array elements: 1 2 3 4 Enter the size 2nd of array: 5 Enter array elements: 5 6 7 8 9 0 The given arrays are disjoint
Method-3: By Using Sorting and Merging
Approach:
- Create scanner class object.
- Ask use length of the array.
- Initialize the array with given size.
- Ask the user for array elements.
- Iterate over the array.
- Sort first array.
- Initialize two pointers, i=0 and j=0.
- Loops over the both the arrays using while loop.
- If current element of arr1 is less than arr2, increment i by one.
- If current element of arr1 is greater than arr2, increment j by one.
- If both are equal return false.
- If the loop is exhausted, return true.
Program:
import java.util.Arrays;
import java.util.Scanner;
public class Main
{
public static void main(String[] args)
{
// create scanner class object
Scanner sc = new Scanner(System.in);
// take input from user for array size
System.out.print("Enter the size 1st of array: ");
int n = sc.nextInt();
// initialize array with size n
int[] a = new int[n];
// take input from user for array elements
System.out.print("Enter array elements: ");
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
System.out.print("Enter the size 2nd of array: ");
int m = sc.nextInt();
// initialize array with size n
int[] b = new int[m];
// take input from user for array elements
System.out.print("Enter array elements: ");
for (int i = 0; i < m; i++) {
b[i] = sc.nextInt();
}
if (checkDisjointSortnMerge(a, b))
System.out.println("The giveen arrays are disjoint.");
else
System.out.println("The given arrays are not disjoint");
}
static boolean checkDisjointSortnMerge(int arr1[], int arr2[])
{
int i = 0, j = 0;
// Sort the given two sets
Arrays.sort(arr1);
Arrays.sort(arr2);
// Check for same elements using
// merge like process
while (i < arr1.length && j < arr2.length)
{
if (arr1[i] < arr2[j])
i++;
else if (arr1[i] > arr2[j])
j++;
else
return false;
}
return true;
}
}
Output: Enter the size 1st of array: 4 Enter array elements: 1 2 3 4 Enter the size 2nd of array: 4 Enter array elements: 4 5 6 7 The given arrays are not disjoint
Grab the opportunity to learn all effective java programming language concepts from basic to advance levels by practicing these Java Program Examples with Output
Related Java Programs: