Dada una array de enteros positivos, la tarea es encontrar un punto/elemento hasta el cual los elementos forman una secuencia estrictamente decreciente, seguida primero por una secuencia de enteros estrictamente crecientes.
- Ambas secuencias deben tener al menos una longitud de 2 (considerando el elemento común).
- El último valor de la secuencia decreciente es el primer valor de la secuencia creciente.
Nota: Imprima «No existe tal elemento», si no se encuentra.
Ejemplos:
Input: arr[] = {3, 2, 1, 2}
Output: 1
{3, 2, 1} is strictly decreasing
then {1, 2} is strictly increasing.
Input: arr[] = {3, 2, 1}
Output: No such element exist
Acercarse:
- Primero comience a recorrer la array y siga recorriendo hasta que los elementos estén en orden estrictamente decreciente.
- Si los siguientes elementos son mayores que el elemento anterior, almacene ese elemento en la variable de punto .
- Comience a atravesar los elementos desde ese punto y continúe hasta que los elementos estén en orden estrictamente creciente.
- Después del paso 3, si todos los elementos se recorren, imprima ese punto.
- De lo contrario, escriba «No existe tal elemento».
Nota: Si cualquiera de los dos elementos es igual, también imprima «No existe tal elemento», ya que debería ser estrictamente decreciente y creciente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check such sequence
int findElement(int a[], int n)
{
// set increasing/decreasing sequence counter to 1
int inc = 1, dec = 1, point;
// for loop counter from 1 to last index of list
for (int i = 1; i < n; i++) {
// check if current int is
// smaller than previous int
if (a[i] < a[i - 1]) {
// if inc is 1, i.e., increasing
// seq. never started
if (inc == 1)
// increase dec by 1
dec++;
else
return -1;
}
// check if current int is greater than previous int
else if (a[i] > a[i - 1]) {
// if inc is 1, i.e., increasing seq.
// starting for first time,
if (inc == 1)
// store a[i-1] in point
point = a[i - 1];
// only if decreasing seq. minimum
// count has been met,
if (dec >= 2)
// increase inc by 1
inc++;
else
// return -1 as decreasing seq.
// min. count must be 2
return -1;
}
// check if current int is equal
// to previous int, if so,
else if (a[i] == a[i - 1])
return -1;
}
// check if inc >= 2 and dec >= 2
// return point
if (inc >= 2 && dec >= 2)
return point;
// otherwise return -1
else
return -1;
}
// Driver code
int main()
{
int arr[] = { 3, 2, 1, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
int ele = findElement(arr, n);
if (ele == -1)
cout << "No such element exist";
else
cout << ele;
return 0;
}
Java
// Java implementation of above approach
public class GFG {
// Function to check such sequence
static int findElement(int a[], int n)
{
// set increasing/decreasing sequence counter to 1
int inc = 1, dec = 1, point = 0;
// for loop counter from 1 to last index of list
for (int i = 1; i < n; i++) {
// check if current int is
// smaller than previous int
if (a[i] < a[i - 1]) {
// if inc is 1, i.e., increasing
// seq. never started
if (inc == 1)
// increase dec by 1
dec++;
else
return -1;
}
// check if current int is greater than previous int
else if (a[i] > a[i - 1]) {
// if inc is 1, i.e., increasing seq.
// starting for first time,
if (inc == 1)
// store a[i-1] in point
point = a[i - 1];
// only if decreasing seq. minimum
// count has been met,
if (dec >= 2)
// increase inc by 1
inc++;
else
// return -1 as decreasing seq.
// min. count must be 2
return -1;
}
// check if current int is equal
// to previous int, if so,
else if (a[i] == a[i - 1])
return -1;
}
// check if inc >= 2 and dec >= 2
// return point
if (inc >= 2 && dec >= 2)
return point;
// otherwise return -1
else
return -1;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 3, 2, 1, 2 };
int n = arr.length ;
int ele = findElement(arr, n);
if (ele == -1)
System.out.println("No such element exist");
else
System.out.println(ele);
}
// This Code is contributed by ANKITRAI1
}
Python
# Python implementation of above approach
def findElement(a, n):
# set increasing sequence counter to 1
inc = 1
# set decreasing sequence counter to 1
dec = 1
# for loop counter from 1 to last
# index of list [len(array)-1]
for i in range(1, n):
# check if current int is smaller than previous int
if(a[i] < a[i-1]):
# if inc is 1, i.e., increasing seq. never started,
if inc == 1:
# increase dec by 1
dec = dec + 1
else:
# return -1 since if increasing seq. has started,
# there cannot be a decreasing seq. in a valley
return -1
# check if current int is greater than previous int
elif(a[i] > a[i-1]):
# if inc is 1, i.e., increasing seq.
# starting for first time,
if inc == 1:
# store a[i-1] in point
point = a[i-1]
# only if decreasing seq. minimum count has been met,
if dec >= 2:
# increase inc by 1
inc = inc + 1
else:
# return -1 as decreasing seq. min. count must be 2
return -1
# check if current int is equal to previous int, if so,
elif(a[i] == a[i-1]):
# return false as valley is always
# strictly increasing / decreasing
return -1
# check if inc >= 2 and dec >= 2,
if(inc >= 2 and dec >= 2):
# return point
return point
else:
# otherwise return -1
return -1
a = [2, 1, 2]
n = len(a)
ele = findElement(a, n)
if ( ele == -1 ):
print("No such element exist")
else:
print(ele)
C#
// C# implementation of above approach
using System;
class GFG
{
// Function to check such sequence
static int findElement(int []a, int n)
{
// set increasing/decreasing
// sequence counter to 1
int inc = 1, dec = 1, point = 0;
// for loop counter from 1 to
// last index of list
for (int i = 1; i < n; i++)
{
// check if current int is
// smaller than previous int
if (a[i] < a[i - 1])
{
// if inc is 1, i.e., increasing
// seq. never started
if (inc == 1)
// increase dec by 1
dec++;
else
return -1;
}
// check if current int is greater
// than previous int
else if (a[i] > a[i - 1])
{
// if inc is 1, i.e., increasing
// seq. starting for first time,
if (inc == 1)
// store a[i-1] in point
point = a[i - 1];
// only if decreasing seq.
// minimum count has been met,
if (dec >= 2)
// increase inc by 1
inc++;
else
// return -1 as decreasing
// seq. min. count must be 2
return -1;
}
// check if current int is equal
// to previous int, if so,
else if (a[i] == a[i - 1])
return -1;
}
// check if inc >= 2 and
// dec >= 2, return point
if (inc >= 2 && dec >= 2)
return point;
// otherwise return -1
else
return -1;
}
// Driver code
public static void Main()
{
int []arr = { 3, 2, 1, 2 };
int n = arr.Length ;
int ele = findElement(arr, n);
if (ele == -1)
Console.WriteLine("No such element exist");
else
Console.WriteLine(ele);
}
}
// This code is contributed by Shashank
PHP
<?php
// PHP implementation of above approach
// Function to check such sequence
function findElement(&$a, $n)
{
// set increasing/decreasing
// sequence counter to 1
$inc = 1;
$dec = 1;
// for loop counter from 1
// to last index of list
for ($i = 1; $i < $n; $i++)
{
// check if current int is
// smaller than previous int
if ($a[$i] < $a[$i - 1])
{
// if inc is 1, i.e., increasing
// seq. never started
if ($inc == 1)
// increase dec by 1
$dec++;
else
return -1;
}
// check if current int is greater
// than previous int
else if ($a[$i] > $a[$i - 1])
{
// if inc is 1, i.e., increasing
// seq. starting for first time,
if ($inc == 1)
// store a[i-1] in point
$point = $a[$i - 1];
// only if decreasing seq.
// minimum count has been met,
if ($dec >= 2)
// increase inc by 1
$inc++;
else
// return -1 as decreasing
// seq. min. count must be 2
return -1;
}
// check if current int is equal
// to previous int, if so,
else if ($a[$i] == $a[$i - 1])
return -1;
}
// check if inc >= 2 and
// dec >= 2, return point
if ($inc >= 2 && $dec >= 2)
return $point;
// otherwise return -1
else
return -1;
}
// Driver code
$arr = array(3, 2, 1, 2);
$n = sizeof($arr);
$ele = findElement($arr, $n);
if ($ele == -1)
echo "No such element exist";
else
echo $ele;
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Java Script implementation of above approach
// Function to check such sequence
function findElement(a,n)
{
// set increasing/decreasing sequence counter to 1
let inc = 1, dec = 1, point = 0;
// for loop counter from 1 to last index of list
for (let i = 1; i < n; i++) {
// check if current int is
// smaller than previous int
if (a[i] < a[i - 1]) {
// if inc is 1, i.e., increasing
// seq. never started
if (inc == 1)
// increase dec by 1
dec++;
else
return -1;
}
// check if current int is greater than previous int
else if (a[i] > a[i - 1]) {
// if inc is 1, i.e., increasing seq.
// starting for first time,
if (inc == 1)
// store a[i-1] in point
point = a[i - 1];
// only if decreasing seq. minimum
// count has been met,
if (dec >= 2)
// increase inc by 1
inc++;
else
// return -1 as decreasing seq.
// min. count must be 2
return -1;
}
// check if current int is equal
// to previous int, if so,
else if (a[i] == a[i - 1])
return -1;
}
// check if inc >= 2 and dec >= 2
// return point
if (inc >= 2 && dec >= 2)
return point;
// otherwise return -1
else
return -1;
}
// Driver code
let arr = [3, 2, 1, 2 ];
let n = arr.length ;
let ele = findElement(arr, n);
if (ele == -1)
document.write("No such element exist");
else
document.write(ele);
// This code is contributed by sravan kumar Gottumukkala
</script>
Producción:
1
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por AnkanDas22 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA