Dados tres números enteros positivos L , R y K , la tarea es encontrar el grupo más grande de números palindrómicos del rango [L, R] tal que la diferencia entre el elemento máximo y mínimo presente en el grupo sea menor que K .
Ejemplos:
Entrada: L = 50, R = 78, K = 12
Salida: 2
Explicación:
Todos los números palindrómicos del rango [50, 78] son {55, 66, 77}.
El grupo de números palindrómicos {55, 66} tienen como diferencia entre el elemento máximo y mínimo 11, que es menor que K( = 12).
Por lo tanto, el tamaño del grupo es 2.Entrada: L = 98, R = 112, K = 13
Salida: 3
Enfoque: el problema dado se puede resolver utilizando la búsqueda binaria . Siga los pasos a continuación para resolver el problema:
- Inicialice una array auxiliar , digamos arr[], y almacene todos los números de palíndromo presentes en el rango [L, R] .
- Defina una función, digamos search(arr, X), para encontrar el índice más a la derecha con un valor menor que X :
- Inicialice tres variables, digamos bajo como 0 , alto como (arr.size() – 1) y ans como -1 .
- Iterar hasta bajo ≤ alto y realizar las siguientes operaciones:
- Calcule mid como low+ (high – low)/2 .
- Si el valor en el índice medio es como máximo X , actualice el valor de ans como medio y bajo como (medio + 1) .
- De lo contrario, actualice el valor de high as (mid – 1) .
- Después de completar los pasos anteriores, devuelve el valor de ans como resultado.
- Recorra la array arr[] y realice los siguientes pasos:
- Encuentre el índice más a la derecha, que es menor o igual que (arr[i] + K – 1) usando la función search() y guárdelo en una variable, digamos rightIndex .
- Si el valor de rightIndex no es igual a -1 , actualice el valor de count como el máximo de count y (rightIndex – i + 1) .
- Después de completar los pasos anteriores, imprima el valor de count como resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to search the
// rightmost index of given number
static int search(vector<int> list, int num)
{
int low = 0, high = list.size() - 1;
// Store the rightmost index
int ans = -1;
while (low <= high)
{
// Calculate the mid
int mid = low + (high - low) / 2;
// If given number <= num
if (list[mid] <= num)
{
// Assign ans = mid
ans = mid;
// Update low
low = mid + 1;
}
else
// Update high
high = mid - 1;
}
// return ans
return ans;
}
// Function to check if the given
// number is palindrome or not
bool isPalindrome(int n)
{
int rev = 0;
int temp = n;
// Generate reverse
// of the given number
while (n > 0)
{
rev = rev * 10 + n % 10;
n /= 10;
}
// If n is a palindrome
return rev == temp;
}
// Function to find the maximum size
// of group of palindrome numbers
// having difference between maximum
// and minimum element at most K
int countNumbers(int L, int R, int K)
{
// Stores the all the palindromic
// numbers in the range [L, R]
vector<int> list;
// Traverse over the range [L, R]
for(int i = L; i <= R; i++)
{
// If i is a palindrome
if (isPalindrome(i))
{
// Append the number
// in the list
list.push_back(i);
}
}
// Stores count of maximum
// palindromic numbers
int count = 0;
// Iterate each element in the list
for(int i = 0; i < list.size(); i++)
{
// Calculate rightmost index in
// the list < current element + K
int right_index = search(list,
list[i] + K - 1);
// Check if there is rightmost
// index from the current index
if (right_index != -1)
count = max(count, right_index - i + 1);
}
// Return the count
return count;
}
// Driver Code
int main()
{
int L = 98, R = 112;
int K = 13;
cout << countNumbers(L, R, K);
}
// This code is contributed by ipg2016107
Java
// Java program for the above approach
import java.util.*;
public class Main {
// Function to find the maximum size
// of group of palindrome numbers
// having difference between maximum
// and minimum element at most K
static int countNumbers(int L, int R, int K)
{
// Stores the all the palindromic
// numbers in the range [L, R]
ArrayList<Integer> list
= new ArrayList<>();
// Traverse over the range [L, R]
for (int i = L; i <= R; i++) {
// If i is a palindrome
if (isPalindrome(i)) {
// Append the number
// in the list
list.add(i);
}
}
// Stores count of maximum
// palindromic numbers
int count = 0;
// Iterate each element in the list
for (int i = 0; i < list.size(); i++) {
// Calculate rightmost index in
// the list < current element + K
int right_index
= search(list, list.get(i) + K - 1);
// Check if there is rightmost
// index from the current index
if (right_index != -1)
count = Math.max(count,
right_index - i + 1);
}
// Return the count
return count;
}
// Function to search the
// rightmost index of given number
static int search(
ArrayList<Integer> list, int num)
{
int low = 0, high = list.size() - 1;
// Store the rightmost index
int ans = -1;
while (low <= high) {
// Calculate the mid
int mid = low + (high - low) / 2;
// If given number <= num
if (list.get(mid) <= num) {
// Assign ans = mid
ans = mid;
// Update low
low = mid + 1;
}
else
// Update high
high = mid - 1;
}
// return ans
return ans;
}
// Function to check if the given
// number is palindrome or not
static boolean isPalindrome(int n)
{
int rev = 0;
int temp = n;
// Generate reverse
// of the given number
while (n > 0) {
rev = rev * 10 + n % 10;
n /= 10;
}
// If n is a palindrome
return rev == temp;
}
// Driver Code
public static void main(String args[])
{
int L = 98, R = 112;
int K = 13;
System.out.print(
countNumbers(L, R, K));
}
}
Python3
# Python3 program for the above approach # Function to find the maximum size # of group of palindrome numbers # having difference between maximum # and minimum element at most K def countNumbers(L, R, K): # Stores the all the palindromic # numbers in the range [L, R] list = [] # Traverse over the range [L, R] for i in range(L, R + 1): # If i is a palindrome if (isPalindrome(i)): # Append the number # in the list list.append(i) # Stores count of maximum # palindromic numbers count = 0 # Iterate each element in the list for i in range(len(list)): # Calculate rightmost index in # the list < current element + K right_index = search(list, list[i] + K - 1) # Check if there is rightmost # index from the current index if (right_index != -1): count = max(count, right_index - i + 1) # Return the count return count # Function to search the # rightmost index of given number def search(list, num): low, high = 0, len(list) - 1 # Store the rightmost index ans = -1 while (low <= high): # Calculate the mid mid = low + (high - low) // 2 # If given number <= num if (list[mid] <= num): # Assign ans = mid ans = mid # Update low low = mid + 1 else: # Update high high = mid - 1 # return ans return ans # Function to check if the given # number is palindrome or not def isPalindrome(n): rev = 0 temp = n # Generate reverse # of the given number while (n > 0): rev = rev * 10 + n % 10 n //= 10 # If n is a palindrome return rev == temp # Driver Code if __name__ == '__main__': L, R = 98, 112 K = 13 print(countNumbers(L, R, K)) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the maximum size
// of group of palindrome numbers
// having difference between maximum
// and minimum element at most K
static int countNumbers(int L, int R, int K)
{
// Stores the all the palindromic
// numbers in the range [L, R]
List<int> list = new List<int>();
// Traverse over the range [L, R]
for(int i = L; i <= R; i++)
{
// If i is a palindrome
if (isPalindrome(i))
{
// Append the number
// in the list
list.Add(i);
}
}
// Stores count of maximum
// palindromic numbers
int count = 0;
// Iterate each element in the list
for(int i = 0; i < list.Count; i++)
{
// Calculate rightmost index in
// the list < current element + K
int right_index = search(list,
list[i] + K - 1);
// Check if there is rightmost
// index from the current index
if (right_index != -1)
count = Math.Max(count,
right_index - i + 1);
}
// Return the count
return count;
}
// Function to search the
// rightmost index of given number
static int search(List<int> list, int num)
{
int low = 0, high = list.Count - 1;
// Store the rightmost index
int ans = -1;
while (low <= high)
{
// Calculate the mid
int mid = low + (high - low) / 2;
// If given number <= num
if (list[mid] <= num)
{
// Assign ans = mid
ans = mid;
// Update low
low = mid + 1;
}
else
// Update high
high = mid - 1;
}
// return ans
return ans;
}
// Function to check if the given
// number is palindrome or not
static bool isPalindrome(int n)
{
int rev = 0;
int temp = n;
// Generate reverse
// of the given number
while (n > 0)
{
rev = rev * 10 + n % 10;
n /= 10;
}
// If n is a palindrome
return rev == temp;
}
// Driver Code
public static void Main(string[] args)
{
int L = 98, R = 112;
int K = 13;
Console.WriteLine(countNumbers(L, R, K));
}
}
// This code is contributed by avijitmondal1998
Javascript
<script>
// Javascript program for the above approach
// Function to search the
// rightmost index of given number
function search(list, num)
{
var low = 0, high = list.length - 1;
// Store the rightmost index
var ans = -1;
while (low <= high)
{
// Calculate the mid
var mid = low + (high - low) / 2;
// If given number <= num
if (list[mid] <= num)
{
// Assign ans = mid
ans = mid;
// Update low
low = mid + 1;
}
else
// Update high
high = mid - 1;
}
// return ans
return ans;
}
// Function to check if the given
// number is palindrome or not
function isPalindrome(n)
{
var rev = 0;
var temp = n;
// Generate reverse
// of the given number
while (n > 0)
{
rev = rev * 10 + n % 10;
n = parseInt(n/10);
}
// If n is a palindrome
return rev == temp;
}
// Function to find the maximum size
// of group of palindrome numbers
// having difference between maximum
// and minimum element at most K
function countNumbers(L, R, K)
{
// Stores the all the palindromic
// numbers in the range [L, R]
var list = [];
// Traverse over the range [L, R]
for(var i = L; i <= R; i++)
{
// If i is a palindrome
if (isPalindrome(i))
{
// Append the number
// in the list
list.push(i);
}
}
// Stores count of maximum
// palindromic numbers
var count = 0;
// Iterate each element in the list
for(var i = 0; i < list.length; i++)
{
// Calculate rightmost index in
// the list < current element + K
var right_index = search(list,
list[i] + K - 1);
// Check if there is rightmost
// index from the current index
if (right_index != -1)
count = Math.max(count, right_index - i + 1);
}
// Return the count
return count;
}
// Driver Code
var L = 98, R = 112;
var K = 13;
document.write( countNumbers(L, R, K));
// This code is contributed by noob2000.
</script>
Producción:
3
Complejidad de tiempo: O((R – L) * log(R – L))
Espacio auxiliar: O(R – L)
Publicación traducida automáticamente
Artículo escrito por hemanthswarna1506 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA