Dados dos números enteros L y R , la tarea es contar los números enteros en el rango [L, R] de modo que satisfagan las dos propiedades siguientes:
- El número debe ser un cuadrado perfecto de cualquier número entero .
- Los dígitos del entero deben estar en forma de onda , es decir, sean d1 , d2 , d3 , d4 , d5 los dígitos del entero actual, entonces d1 < d2 > d3 < d4… debe ser cierto.
Ejemplos:
Entrada: L = 1, R = 64
Salida: 7
Explicación:
Los números especiales en el rango [1, 64] son 1, 4, 9, 16, 25, 36 y 49.Entrada: L = 80, R = 82
Salida: 0
Enfoque ingenuo: el enfoque más simple para resolver el problema es recorrer el rango [L, R] y, para cada número en el rango, verificar las dos condiciones anteriores.
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, itere solo sobre cuadrados perfectos y verifique la segunda condición. Siga los pasos a continuación para el enfoque:
- Inicialice una variable digamos, count = 0 , para contar todos los números especiales en el rango [L, R] .
- Iterar sobre todos los cuadrados perfectos que son menores que R .
- Defina una función , digamos check(N) , para verificar si el número N satisface la segunda condición iterando sobre dígitos pares e impares.
- Aumente el conteo , si el número es mayor que L y la función de verificación devuelve verdadero para el número dado.
- Por último, devuelve la cuenta .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for 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 calculate total
// integer in the given range
int totalUniqueNumber(int L, int R)
{
// Base case
if (R <= 0) {
return 0;
}
// Current number
int cur = 1;
// Variable to store
// total unique numbers
int count = 0;
// Iterating over perfect
// squares
while ((cur * cur) <= R) {
int num = cur * cur;
// If number is greater
// than L and satisfies
// required conditions
if (num >= L && check(num)) {
count++;
}
// Moving to the
// next number
cur++;
}
// Return Answer
return count;
}
// Driver Code
int main()
{
int L = 1, R = 64;
cout << totalUniqueNumber(L, R);
}
Java
// Java program for the above approach
import java.util.*;
public 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) == 1) {
// 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) == 1) {
// 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 calculate total
// integer in the given range
static int totalUniqueNumber(int L, int R)
{
// Base case
if (R <= 0) {
return 0;
}
// Current number
int cur = 1;
// Variable to store
// total unique numbers
int count = 0;
// Iterating over perfect
// squares
while ((cur * cur) <= R) {
int num = cur * cur;
// If number is greater
// than L and satisfies
// required conditions
if (num >= L && check(num)) {
count++;
}
// Moving to the
// next number
cur++;
}
// Return Answer
return count;
}
// Driver Code
public static void main(String args[])
{
int L = 1, R = 64;
// Function call
System.out.println(totalUniqueNumber(L, R));
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# Python program 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 (S[i] >= 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) == 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: prev = i - 1; next = i + 1; if ((i & 1) == 1): # Character is a # local maximum if ((S[i] > S[prev]) and (S[i] > S[next])): return True; else: return False; else: # Character is a # local minimum if ((S[i] < S[prev]) and (S[i] < S[next])): return True; else: return False; return True; # Function to calculate total # integer in the given range def totalUniqueNumber(L, R): # Base case if (R <= 0): return 0; # Current number cur = 1; # Variable to store # total unique numbers count = 0; # Iterating over perfect # squares while ((cur * cur) <= R): num = cur * cur; # If number is greater # than L and satisfies # required conditions if (num >= L and check(num)): count += 1; # Moving to the # next number cur += 1; # Return Answer return count; # Driver Code if __name__ == '__main__': L = 1; R = 64; # Function call print(totalUniqueNumber(L, R)); # This code is contributed by gauravrajput1
C#
// C# program for the above approach
using System;
using System.Collections;
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) == 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) == 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 calculate total
// integer in the given range
static int totalUniqueNumber(int L, int R)
{
// Base case
if (R <= 0) {
return 0;
}
// Current number
int cur = 1;
// Variable to store
// total unique numbers
int count = 0;
// Iterating over perfect
// squares
while ((cur * cur) <= R) {
int num = cur * cur;
// If number is greater
// than L and satisfies
// required conditions
if (num >= L && check(num)) {
count++;
}
// Moving to the
// next number
cur++;
}
// Return Answer
return count;
}
// Driver Code
public static void Main()
{
int L = 1, R = 64;
// Function call
Console.Write(totalUniqueNumber(L, R));
}
}
// This code is contributed by Samim Hossain Mondal.
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] >= S[next]) {
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] <= S[prev]) {
return false;
}
}
else {
// Character is a
// local minimum
if (S[i] >= S[prev]) {
return false;
}
}
}
}
else {
let prev = i - 1;
let 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 calculate total
// integer in the given range
function totalUniqueNumber(L, R) {
// Base case
if (R <= 0) {
return 0;
}
// Current number
let cur = 1;
// Variable to store
// total unique numbers
let count = 0;
// Iterating over perfect
// squares
while ((cur * cur) <= R) {
let num = cur * cur;
// If number is greater
// than L and satisfies
// required conditions
if (num >= L && check(num)) {
count++;
}
// Moving to the
// next number
cur++;
}
// Return Answer
return count;
}
// Driver Code
let L = 1, R = 64;
document.write(totalUniqueNumber(L, R));
// This code is contributed by Potta Lokesh
</script>
Producción
7
Complejidad de tiempo: O(sqrt(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA