Dados los números enteros L y R , encuentre todos los números en el rango L a R cuyos dígitos sean crecientes o decrecientes alternativamente, es decir, si los dígitos en el número actual son d1, d2, d3, d4, d5 . . . entonces d1 < d2 > d3 < d4. . . debe ser cierto.
Ejemplos:
Entrada: L = 60, R = 100
Salida: 67 68 69 78 79 89
Explicación: estos números siguen la forma creciente y decreciente de dígitosEntrada: L = 4, R = 12
Salida: 4 5 6 7 8 9 12
Enfoque: recorre todos los números en el rango L a R y encuentra los números con el patrón de dígitos dado. Siga los pasos que se mencionan a continuación:
- Recorre cada dígito en el número
- Compruebe si el carácter en dos índices por delante está aumentando desde el carácter actual,
- De lo contrario, verifique si el carácter en dos índices por delante está disminuyendo desde el carácter actual
- Si ambos casos son falsos, rompa y verifique el siguiente número
- Si todos los casos son verdaderos, escriba el número
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Utility function to check if
// the digits of the current
// integer forms a wave pattern
bool check(int N)
{
// Convert the number to a string
string S = to_string(N);
// Loop to iterate over digits
for (int i = 0; i < S.size(); i++) {
if (i == 0) {
// Next character of
// the number
int next = i + 1;
// Current character is
// not a local minimum
if (next < S.size()) {
if (S[i] >= S[next]) {
return false;
}
}
}
else if (i == S.size() - 1) {
// Previous character of
// the number
int prev = i - 1;
if (prev >= 0) {
// Character is a
// local maximum
if (i & 1) {
// Character is not
// a local maximum
if (S[i] <= S[prev]) {
return false;
}
}
else {
// Character is a
// local minimum
if (S[i] >= S[prev]) {
return false;
}
}
}
}
else {
int prev = i - 1;
int next = i + 1;
if (i & 1) {
// Character is a
// local maximum
if ((S[i] > S[prev]) &&
(S[i] > S[next])) {
}
else {
return false;
}
}
else {
// Character is a
// local minimum
if ((S[i] < S[prev]) &&
(S[i] < S[next])) {
}
else {
return false;
}
}
}
}
return true;
}
// Function to find the numbers
void findNumbers(int L, int R)
{
for (int i = L; i <= R; i++)
if (check(i))
cout << i << " ";
}
// Driver Code
int main()
{
int L = 60, R = 100;
findNumbers(L, R);
return 0;
}
Java
// Java code to implement the above approach
class GFG
{
// Utility function to check if
// the digits of the current
// integer forms a wave pattern
static boolean check(int N)
{
// Convert the number to a string
String S = Integer.toString(N);
// Loop to iterate over digits
for (int i = 0; i < S.length(); i++) {
if (i == 0) {
// Next character of
// the number
int next = i + 1;
// Current character is
// not a local minimum
if (next < S.length()) {
if (S.charAt(i) >= S.charAt(next)) {
return false;
}
}
}
else if (i == S.length() - 1) {
// Previous character of
// the number
int prev = i - 1;
if (prev >= 0) {
// Character is a
// local maximum
if ((i & 1) > 0) {
// Character is not
// a local maximum
if (S.charAt(i) <= S.charAt(prev)) {
return false;
}
} else {
// Character is a
// local minimum
if (S.charAt(i) >= S.charAt(prev)) {
return false;
}
}
}
} else {
int prev = i - 1;
int next = i + 1;
if ((i & 1) > 0) {
// Character is a
// local maximum
if ((S.charAt(i) > S.charAt(prev)) &&
(S.charAt(i) > S.charAt(next))) {
} else {
return false;
}
} else {
// Character is a
// local minimum
if ((S.charAt(i) < S.charAt(prev)) &&
(S.charAt(i) < S.charAt(next))) {
} else {
return false;
}
}
}
}
return true;
}
// Function to find the numbers
static void findNumbers(int L, int R) {
for (int i = L; i <= R; i++)
if (check(i))
System.out.print(i + " ");
}
// Driver Code
public static void main(String args[]) {
int L = 60, R = 100;
findNumbers(L, R);
}
}
// This code is contributed by gfgking.
Python3
# Python code for the above approach
# Utility function to check if
# the digits of the current
# integer forms a wave pattern
def check(N):
# Convert the number to a string
S = str(N);
# Loop to iterate over digits
for i in range(len(S)):
if (i == 0):
# Next character of
# the number
next = i + 1;
# Current character is
# not a local minimum
if (next < len(S)):
if (ord(S[i]) >= ord(S[next])):
return False;
elif (i == len(S) - 1):
# Previous character of
# the number
prev = i - 1;
if (prev >= 0):
# Character is a
# local maximum
if (i & 1):
# Character is not
# a local maximum
if (ord(S[i]) <= ord(S[prev])):
return False;
else:
# Character is a
# local minimum
if (ord(S[i]) >= ord(S[prev])):
return False;
else:
prev = i - 1;
next = i + 1;
if (i & 1):
# Character is a
# local maximum
if (ord(S[i]) > ord(S[prev])) and (ord(S[i]) > ord(S[next])):
print("", end="")
else:
return False;
else:
# Character is a
# local minimum
if (ord(S[i]) < ord(S[prev])) and (ord(S[i]) < ord(S[next])):
print("", end="")
else:
return False;
return True;
# Function to find the numbers
def findNumbers(L, R):
for i in range(L, R + 1):
if (check(i)):
print(i, end= " ")
# Driver Code
L = 60
R = 100;
findNumbers(L, R);
# This code is contributed by Saurabh Jaiswal
C#
// C# code to implement the above approach
using System;
class GFG
{
// Utility function to check if
// the digits of the current
// integer forms a wave pattern
static bool check(int N)
{
// Convert the number to a string
string S = N.ToString();
// Loop to iterate over digits
for (int i = 0; i < S.Length; i++) {
if (i == 0) {
// Next character of
// the number
int next = i + 1;
// Current character is
// not a local minimum
if (next < S.Length) {
if (S[i] >= S[next]) {
return false;
}
}
}
else if (i == S.Length - 1) {
// Previous character of
// the number
int prev = i - 1;
if (prev >= 0) {
// Character is a
// local maximum
if ((i & 1) > 0) {
// Character is not
// a local maximum
if (S[i] <= S[prev]) {
return false;
}
}
else {
// Character is a
// local minimum
if (S[i] >= S[prev]) {
return false;
}
}
}
}
else {
int prev = i - 1;
int next = i + 1;
if ((i & 1) > 0) {
// Character is a
// local maximum
if ((S[i] > S[prev]) &&
(S[i] > S[next])) {
}
else {
return false;
}
}
else {
// Character is a
// local minimum
if ((S[i] < S[prev]) &&
(S[i] < S[next])) {
}
else {
return false;
}
}
}
}
return true;
}
// Function to find the numbers
static void findNumbers(int L, int R)
{
for (int i = L; i <= R; i++)
if (check(i))
Console.Write(i + " ");
}
// Driver Code
public static void Main()
{
int L = 60, R = 100;
findNumbers(L, R);
}
}
// This code is contributed by Samim Hossain Monda
Javascript
<script>
// JavaScript code for the above approach
// Utility function to check if
// the digits of the current
// integer forms a wave pattern
function check(N)
{
// Convert the number to a string
let S = N.toString();
// Loop to iterate over digits
for (let i = 0; i < S.length; i++)
{
if (i == 0)
{
// Next character of
// the number
let next = i + 1;
// Current character is
// not a local minimum
if (next < S.length)
{
if (S[i].charCodeAt(0) >= S[next].charCodeAt(0))
{
return false;
}
}
}
else if (i == S.length - 1)
{
// Previous character of
// the number
let prev = i - 1;
if (prev >= 0) {
// Character is a
// local maximum
if (i & 1) {
// Character is not
// a local maximum
if (S[i].charCodeAt(0) <= S[prev].charCodeAt(0)) {
return false;
}
}
else {
// Character is a
// local minimum
if (S[i].charCodeAt(0) >= S[prev].charCodeAt(0)) {
return false;
}
}
}
}
else {
let prev = i - 1;
let next = i + 1;
if (i & 1) {
// Character is a
// local maximum
if ((S[i].charCodeAt(0) > S[prev].charCodeAt(0)) &&
(S[i].charCodeAt(0) > S[next].charCodeAt(0))) {
}
else {
return false;
}
}
else {
// Character is a
// local minimum
if ((S[i].charCodeAt(0) < S[prev].charCodeAt(0)) &&
(S[i].charCodeAt(0) < S[next].charCodeAt(0))) {
}
else {
return false;
}
}
}
}
return true;
}
// Function to find the numbers
function findNumbers(L, R) {
for (let i = L; i <= R; i++)
if (check(i))
document.write(i + " ")
}
// Driver Code
let L = 60, R = 100;
findNumbers(L, R);
// This code is contributed by Potta Lokesh
</script>
Producción
67 68 69 78 79 89
Complejidad de tiempo: O((RL) * D) donde D es el número de dígitos en R
Espacio auxiliar: O(D)