Check if the array is beautiful
Given an integer n and an array of size n check if it satisfies following conditions:-
- All elements of array must lie between 1 to n.
- Array must NOT be sorted in ascending order.
- The array consists of unique elements.
If all conditions satisfied print Yes else No.
Examples:
Input: 4
1 2 3 4
Output: No
Array is sorted in ascending order
Input: 4
4 3 2 1
Output: Yes
Satisfies all given condition
Input: 4
1 1 2 3
Output: No
Array has repeated entries
A simple solution is to count frequency of all elements. While counting frequency check if all elements are from 1 to n. Finally check if frequency of every element is 1 or not and array is sorted in ascending order or not.
Below is the implementation
// CPP program to check array is
// beautiful or not
#include <bits/stdc++.h>
using namespace std;
// Function to implement the given task
bool isBeautiful(int a[], int n)
{
// count the frequency and check if all elements are in
// between 1 to n
unordered_map<int, int> m;
bool isAscending = true;
for (int i = 0; i < n; i++) {
if ((a[i] < 1 || a[i] > n) && m.find(a[i])==m.end())
return false;
m[a[i]]++;
if(i != 0 && a[i] < a[i - 1]){
isAscending = false;
}
}
return !isAscending;
}
// Driver Code
int main()
{
int a[] = { 1, 2, 4, 3 };
int n = sizeof(a) / sizeof(a[0]);
if (isBeautiful(a, n))
cout << "Yes";
else
cout << "No";
return 0;
}
// This is contributed by Arpit Jain
/*package whatever //do not write package name here */
import java.util.*;
class GFG
{
// Function to implement the given task
static boolean isBeautiful(int a[], int n)
{
// count the frequency and check if all elements are in
// between 1 to n
boolean isAscending = true;
HashMap<Integer,Integer> m = new HashMap<>();
for (int i = 0; i < n; i++) {
if ((a[i] < 1 || a[i] > n) && !m.containsKey(a[i]))
return false;
m.put(a[i],m.getOrDefault(a[i],0)+1);
if(i!=0 && a[i]<a[i-1])
isAscending=false;
}
return !isAscending;
}
public static void main (String[] args) {
int a[] = { 1, 2, 4, 3 };
int n = a.length;
if (isBeautiful(a, n))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by aadityaburujwale.
# Python program to check array is
# beautiful or not
# Function to implement the given task
def isBeautiful(a, n):
# count the frequency and check if all elements are in
# between 1 to n
isAscending = True
m = {}
for i in range(n):
if(a[i] < 1 or a[i] > n) and ( a[i] not in m):
return false
m[a[i]] = m.get(a[i], 0) + 1
if (i != 0) and (a[i] < a[i - 1]):
isAscending = False
return (isAscending == False )
# Driver Code
a = [1, 2, 4, 3]
n = len(a)
if isBeautiful(a, n):
print("Yes")
else:
print("No")
# This code is contributed by akashish__
using System;
using System.Collections.Generic;
public class GFG {
// Function to implement the given task
static bool isBeautiful(int[] a, int n)
{
// count the frequency and check if all elements are
// in between 1 to n
bool isAscending = true;
Dictionary<int, int> m = new Dictionary<int, int>();
for (int i = 0; i < n; i++) {
if ((a[i] < 1 || a[i] > n) && !m.ContainsKey(a[i]))
return false;
m.Add(a[i], 1);
if(i!=0 && a[i]<a[i-1])
isAscending = false;
}
return !isAscending;
}
static public void Main()
{
int[] a = { 1, 2, 4, 3 };
int n = a.Length;
if (isBeautiful(a, n))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by akashish__
// JavaScript program to check array is
// beautiful or not
// Function to implement the given task
function isBeautiful(a, n) {
// count the frequency and check if all elements are in
// between 1 to n
let isAscending = true;
let m = new Map();
for (let i = 0; i < n; i++) {
if ((a[i] < 1 || a[i] > n) && !m.has(a[i]))
return false;
m.set(a[i], m.get(a[i] || 0) + 1);
if(i !== 0 && a[i] < a[i-1] ){
isAscending = false;
}
}
return !isAscending;
}
// Driver Code
let a = [ 1, 2, 4, 3 ];
let n = a.length;
if (isBeautiful(a, n))
console.log("Yes");
else
console.log("No");
// This is contributed by akashish__
Output
Yes
Time Complexity: O(n)
Auxiliary Space: O(n)
An efficient solution is to avoid extra space.
Implementation:
// CPP program to check array is
// beautiful or not
#include <iostream>
using namespace std;
// Function to implement the given task
bool isBeautiful(int a[], int n)
{
int sum = a[0];
bool isAscSorted = true;
for (int i = 1; i < n; i++) {
// Checking for any repeated entry
if (a[i] <= 0 || a[i] > n || a[i] == a[i - 1])
return 0;
// Checking for ascending sorting
if (a[i] < a[i - 1])
isAscSorted = false;
sum += a[i];
}
// Does not satisfy second condition
if (isAscSorted == true)
return false;
// Sum of 1 to n elements is
// (n*(n + 1)/2))
return (sum == (n * (n + 1) / 2));
}
// Driver Code
int main()
{
int a[] = { 1, 2, 4, 3 };
int n = sizeof(a) / sizeof(a[0]);
if (isBeautiful(a, n))
cout << "Yes";
else
cout << "No";
return 0;
}
// Java program to check array is
// beautiful or not
import java.io.*;
class GFG {
// Function to implement the given task
static boolean isBeautiful(int a[], int n)
{
int sum = a[0];
boolean isAscSorted = true;
for (int i = 1; i < n; i++) {
// Checking for any repeated entry
if (a[i] == a[i - 1])
return false;
// Checking for ascending sorting
if (a[i] < a[i - 1])
isAscSorted = false;
sum += a[i];
}
// Does not satisfy second condition
if (isAscSorted == true)
return false;
// Sum of 1 to n elements is
// (n*(n + 1)/2))
return (sum == (n * (n + 1) / 2));
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 1, 2, 4, 3 };
int n = a.length;
if (isBeautiful(a, n))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by vt_m
# Python program to check array is
# beautiful or not
# Function to implement the given task
def isBeautiful(a, n):
sum = a[0]
isAscSorted = True
for i in range(1, n):
# Checking for any repeated entry
if (a[i] == a[i - 1]):
return False
# Checking for ascending sorting
if (a[i] < a[i - 1]):
isAscSorted = False
sum = sum + a[i]
# Does not satisfy second condition
if (isAscSorted == True):
return False
# Sum of 1 to n elements is
# (n*(n + 1)/2))
return (sum == (n * (n + 1) // 2))
# Driver code
a = [1, 2, 4, 3]
n = len(a)
if (isBeautiful(a, n)):
print("Yes")
else:
print("No")
# This code is contributed
# by Anant Agarwal.
// C# program to check array is
// beautiful or not
using System;
class GFG {
// Function to implement the given task
static bool isBeautiful(int[] a, int n)
{
int sum = a[0];
bool isAscSorted = true;
for (int i = 1; i < n; i++) {
// Checking for any repeated entry
if (a[i] == a[i - 1])
return false;
// Checking for ascending sorting
if (a[i] < a[i - 1])
isAscSorted = false;
sum += a[i];
}
// Does not satisfy second condition
if (isAscSorted == true)
return false;
// Sum of 1 to n elements is
// (n*(n + 1)/2))
return (sum == (n * (n + 1) / 2));
}
// Driver Code
public static void Main()
{
int[] a = { 1, 2, 4, 3 };
int n = a.Length;
if (isBeautiful(a, n))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by vt_m
<script>
// Javascript program to check array is
// beautiful or not
// Function to implement the given task
function isBeautiful(a, n) {
var sum = a[0];
var isAscSorted = true;
for (var i = 1; i < n; i++) {
// Checking for any repeated entry
if (a[i] == a[i - 1])
return 0;
// Checking for ascending sorting
if (a[i] < a[i - 1])
isAscSorted = false;
sum += a[i];
}
// Does not satisfy second condition
if (isAscSorted == true)
return false;
// Sum of 1 to n elements is
// (n*(n + 1)/2))
return (sum == (n * (n + 1) / 2));
}
// Driver Code
var a = [1, 2, 4, 3];
var n = a.length;
if (isBeautiful(a, n))
document.write( "Yes");
else
document.write( "No");
</script>
<?php
// PHP program to check array is
// beautiful or not
// Function to implement
// the given task
function isBeautiful($a, $n)
{
$sum = $a[0];
$sAscSorted = true;
for ($i = 1; $i < $n; $i++)
{
// Checking for any repeated entry
if ($a[$i] == $a[$i - 1])
return 0;
// Checking for ascending sorting
if ($a[$i] < $a[$i - 1])
$isAscSorted = false;
$sum += $a[$i];
}
// Does not satisfy second condition
if ($isAscSorted == true)
return false;
// Sum of 1 to n elements is
// (n*(n + 1)/2))
return ($sum == ($n * ($n + 1) / 2));
}
// Driver Code
$a = array(1, 2, 4, 3);
$n = count($a);
if (isBeautiful($a, $n))
echo "Yes";
else
echo "No";
// This code is contributed by Sam007
?>
Output
Yes
Time Complexity: O(n)
Auxiliary Space: O(1)
Contact Us