Beautiful Array in Java
In this section, we will be acknowledged about the beautiful array in Java, its characteristics, how it is achieved. What are the types of approaches and what are the tools or the packages required for the implementation of each and every approach? The word Beautiful is a word we daily use to describe people, things and many more but here in the programming languages it simply means perfection and ambiguity less.
Beautiful Array
If an array of size s satisfies the following criteria, it is referred to as a beautiful array:
- The range of the array's items must be from 1 to n.
- Sorting an array in ascending order is NOT allowed.
- There are distinct components in the array.
Let understand it through examples.
Example1:
arr[]= [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Size of array = 10
The above array is not said to be a beautiful array.
Reason: The array's elements are sorted in ascending order considering that each element is unique and falls within the range of 1 to size. Hence, failing the condition. As a result, the provided array is not a beautiful array.
Example2:
Arr[] = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
Size of array = 10
The above array is said to be a beautiful array because array's elements are all contained in the size range, from 1 to size. As a result, condition 1 is met. All of the components are unique. As a result, condition 2 is met. Additionally, the array's elements are not all ordered in ascending order. As a result, condition 3 is indeed achieved. As a result, each of the aforementioned requirements is met, which supports that the given array is a beautiful array.
In Java, to implement a beautiful array there exists three methods. They are
- By sorting method
- By HashMap method
- By leveraging the Sum of n Natural Numbers
By Sorting Method
- Having similar size as the input array, create an auxiliary array.
- With the support of a loop, copy each element out from input array towards the auxiliary array. It also determines whether or not each component of the array falls within the range of 1 to size s during copying. In that case, we can conclude that the input array is not beautiful array. As a result, step 3 is not necessary. Step 3 should be taken if each element is inside the range.
- Sort the auxiliary array.
- Working with the input array, begin comparing items of a auxiliary array using a loop. Check the array's elements for uniqueness within the loop as well.
- The elements are said to be placed in ascending order if the arrangement of the input array's items exactly matches the sequence of the auxiliary array's components. Consequently, this input array is indeed not beautiful array.
- The array is really not identifiable if there are several copies of an element.
- We can argue that now the input array seems beautiful if somehow the elements are not ordered in ascending order and there are no duplicates.
Let us understand it with a basic example program
File name: SortMeth.java
// Java application to determine whether an array is beautiful
import java.io.*;
class SortMeth {
// Method to carry out the specified task
static boolean isBeautiful(int a[], int n)
{
int sum = a[0];
boolean isAscSorted = true;
for (int i = 1; i < n; i++) {
// checking for duplicate elements
if (a[i] == a[i - 1])
return false;
// Verifying ascending sorting
if (a[i] < a[i - 1])
isAscSorted = false;
sum += a[i];
}
// Does not fulfill the second requirement.
if (isAscSorted == true)
return false;
return (sum == (n * (n + 1) / 2));
}
public static void main(String[] args)
{
int a[] = { 9, 7, 3, 5, 6 };
int n = a.length;
if (isBeautiful(a, n))
System.out.println("Yes, the provided array is a beautiful array");
else
System.out.println("No, the provided array is not a beautiful array");
}
}Output
No, the provided array is not a beautiful array
The above program has an O(n * log(n)) time complexity due to sorting. The preceding program's space complexity is O(n), while n is the maximum number of elements in the input array, because we are also employing an auxiliary array.
By HashMap Method
The time complexity for the above approach can be minimized by saving the frequency of appearance of the elements. Its algorithm is explained as below.
- Make a hash table. The elements in the input array will serve as the hash map's key, while the count of instances of each element will serve as its value.
- Start by iterating through the input array's elements in a for loop, storing each one along with its total number of occurrences in the hash map. Check whether the element's value falls inside the range while recording the count of occurrences. Check the order of the elements as well as whether or not each element occurs more than once in the count.
- We can claim that now the input array is therefore not beautiful if the count of any element's occurrences is larger than 1, the elements are sorted in increasing order, or even any element does not fall within the range; otherwise, lovely.
Let us understand it with a basic example program
File name: HashMeth.java
// Java application to determine whether an array is beautiful
import java.util.HashMap;
public class HashMeth
{
// a procedure to determine that whether supplied array becomes beautiful or not
public boolean isBeautiful(int inputArr[])
{
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
int size = inputArr.length;
boolean isAscending = true;
for(int i = 0; i < size; i++)
{
// The input array's elements must all fall between 1 and size.
if(inputArr[i] >= 1 && inputArr[i] <= size)
{
if(hm.containsKey(inputArr[i]))
{
// We obtained at least two of each ingredient. Consequently, the given array is //indeed not Beautiful.
return false;
}
else
{
hm.put(inputArr[i] , 1);
}
}
else
{
// When the control reaches this location, at least single element inside the input //array is considered to have left the range. We can therefore return false;
return false;
}
if(i != 0 && inputArr[i] < inputArr[i - 1])
{
isAscending = false;
}
}
if(!isAscending)
{
return true;
}
return false;
}
public static void main(String argvs[])
{
int inputArr[] = {10,9,8,7,6,5,4,3,2,1};
BeautifulArray1 obj = new BeautifulArray1();
int s = inputArr.length;
System.out.print("The considered input array is: \n{ ");
for(int i = 0; i < s; i++)
{
System.out.print(inputArr[i] + " ");
}
System.out.print("}");
if(obj.isBeautiful(inputArr))
{
System.out.println(" is beautiful.");
}
else
{
System.out.println(" is not beautiful.");
}
System.out.println(" \n");
int inputArr1[] = {1, 2, 3, 4, 5, 6, 7, 8, 19, 10};
s = inputArr1.length;
System.out.print("The considered input array is: \n{ ");
for(int i = 0; i < s; i++)
{
System.out.print(inputArr1[i] + " ");
}
System.out.print("}");
if(obj.isBeautiful(inputArr1))
{
System.out.println(" is beautiful.");
}
else
{
System.out.println(" is not beautiful.");
}
System.out.println(" \n");
int inputArr2[] = {10,9,8,7,6,1,2,3,4,5};
s = inputArr2.length;
System.out.print("The considered input array is: \n{ ");
for(int i = 0; i < s; i++)
{
System.out.print(inputArr2[i] + " ");
}
System.out.print("}");
if(obj.isBeautiful(inputArr2))
{
System.out.println(" is beautiful.");
}
else
{
System.out.println(" is not beautiful.");
}
System.out.println(" \n");
int inputArr3[] = {1,2,3,4,5,10,9,8,7,6};
s = inputArr3.length;
System.out.print("The considered input array is: \n{ ");
for(int i = 0; i < s; i++)
{
System.out.print(inputArr3[i] + " ");
}
System.out.print("}");
if(obj.isBeautiful(inputArr3))
{
System.out.println(" is beautiful.");
}
else
{
System.out.println(" is not beautiful.");
}
}
}
Output
The considered input array is:
{ 10 9 8 7 6 5 4 3 2 1 } is beautiful.
The considered input array is:
{ 1 2 3 4 5 6 7 8 19 10 } is not beautiful.
The considered input array is:
{ 10 9 8 7 6 1 2 3 4 5 } is beautiful.
The considered input array is:
{ 1 2 3 4 5 10 9 8 7 6 } is beautiful.
The program's temporal complexity is O(n), as a single loop is used to find the input array's beauty. The above mentioned application further stores the element and its frequency in a hash map. With n being the maximum number of elements in the array, the space complexity is similarly O(n).
We still have scope for improvement in regard to space complexity. Keep in mind the following strategy.
By leveraging the sum of n numbers
The provided information can be utilized to perform more optimization. It has previously been stated in the issue that an array's elements must range from 1 to n in order to be lovely (length of an array). As a result, the very first n real numbers together with the total of all the constituents must be equal. If the total is greater than or less than zero, this indicates that some elements are either outside of the acceptable range or are recurring.
Consider the input array: 1, 2, 3, 4, and 5. The size is 5. Since the first five natural numbers are divisible by two, their sum is (5 * (5 + 1)) / 2 = (5 * 6) / 2 = 30 / 2 = 15, which equals 1 + 2 + 3 + 4 + 5. A value which is not equal to exactly 10 is obtained if any further elements are removed from the input array or repeated.
Suppose in the considered input array {1, 2, 3, 5, 6}. Here, we've taken 6 in place of 4. This results in a sum of 1 + 2 + 3 + 5 + 6 = 17, a number that isn't the same as 15.
If we consider components that are repeated, such as that we have taken the number 2 twice and plucked out the number 3, therefore the summation result of considered input array will be = 1 + 2 + 2 + 4 + 5 is 14, which is once more not equal to 15.
As a result, we can see that duplication of items and elements falling out of range are both eliminated whenever the sum of an array's elements equals the summation of the primary n natural numbers.
The only thing left to do is to confirm whether or not the elements are arranged in ascending order. The same is displayed in the application below.
File name: SumMeth.java
public class SumMeth
{
// a procedure that determines whether a given array really beautiful or not
public boolean isBeautiful(int inputArr[])
{
int size = inputArr.length;
int sumOfnNaturalNo = ((size * (size + 1))) / 2;
boolean isAscending = true;
int sumOfInputArrEle = 0;
for(int i = 0; i < size; i++)
{
sumOfInputArrEle = sumOfInputArrEle + inputArr[i];
// verifying whether the elements in the input array are arranged in ascending order //or not.
if(i != 0 && inputArr[i] < inputArr[i - 1])
{
isAscending = false;
}
}
if(!isAscending && (sumOfInputArrEle == sumOfnNaturalNo))
{
return true;
}
return false;
}
public static void main(String argvs[])
{
int inputArr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
// going to generate a SumMeth class object
SumMeth obj = new SumMeth();
int s = inputArr.length;
System.out.print("The considered input array is: \n{ ");
for(int i = 0; i < s; i++)
{
System.out.print(inputArr[i] + " ");
}
System.out.print("}");
if(obj.isBeautiful(inputArr))
{
System.out.println(" is beautiful.");
}
else
{
System.out.println(" is not beautiful.");
}
System.out.println(" \n");
int inputArr1[] = {10,9,8,7,6,5,4,3,2,1};
s = inputArr1.length;
System.out.print("The considered input array is: \n{ ");
for(int i = 0; i < s; i++)
{
System.out.print(inputArr1[i] + " ");
}
System.out.print("}");
if(obj.isBeautiful(inputArr1))
{
System.out.println(" is beautiful.");
}
else
{
System.out.println(" is not beautiful.");
}
System.out.println(" \n");
int inputArr2[] = {1, 2, 3, 4, 5,10,9,8,7,6};
s = inputArr2.length;
System.out.print("The considered input array is: \n{ ");
for(int i = 0; i < s; i++)
{
System.out.print(inputArr2[i] + " ");
}
System.out.print("}");
if(obj.isBeautiful(inputArr2))
{
System.out.println(" is beautiful.");
}
else
{
System.out.println(" is not beautiful.");
}
System.out.println(" \n");
int inputArr3[] = {10,9,8,7,6,1,2,3,4,5};
s = inputArr3.length;
System.out.print("The considered input array is: \n{ ");
for(int i = 0; i < s; i++)
{
System.out.print(inputArr3[i] + " ");
}
System.out.print("}");
if(obj.isBeautiful(inputArr3))
{
System.out.println(" is beautiful.");
}
else
{
System.out.println(" is not beautiful.");
}
}
} Output
The considered input array is:
{ 1 2 3 4 5 6 7 8 9 10 } is not beautiful.
The considered input array is:
{ 10 9 8 7 6 5 4 3 2 1 } is beautiful.
The considered input array is:
{ 1 2 3 4 5 10 9 8 7 6 } is beautiful.
The considered input array is:
{ 10 9 8 7 6 1 2 3 4 5 } is beautiful.The program's time complexity is O(n), where n is the maximum number of elements in the input array, and we find the input array to be lovely in a single loop. The above- mentioned application uses no additional storage to check the lovely array. Accordingly, the program's space complexity becomes O (1).