Longest Square Streak en un Array

En este artículo, te mostramos cómo solucionar el problema Longest Square Streak in an Array utilizando un enfoque eficiente en Java. Este problema es común en plataformas como LeetCode.

Descripción del Problema

Se te da un array de enteros nums. Una subsecuencia de nums se llama racha de cuadrados si:

• La longitud de la subsecuencia es al menos 2, y
• Después de ordenar la subsecuencia, cada elemento (excepto el primero) es el cuadrado del número anterior.

Debes devolver la longitud de la racha de cuadrados más larga en nums, o devolver -1 si no hay ninguna racha de cuadrados.

Enfoque de la Solución

La clave para resolver este problema es utilizar un HashSet para almacenar los números con el fin de verificar rápidamente si el cuadrado de un número ya está presente en el array. Luego, recorrernos el array, y para cada número, intentamos construir la racha más larga posible a partir de ese número.

Código en Java

import java.util.HashSet;

public class LongestSquareStreak {
    public int longestSquareStreak(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int maxLength = -1;

        for (int num : nums) {
            int currentNum = num;
            int count = 0;

            while (set.contains(currentNum)) {
                count++;
                currentNum = currentNum * currentNum;
            }

            if (count >= 2) {
                maxLength = Math.max(maxLength, count);
            }
        }

        return maxLength;
    }

    public static void main(String[] args) {
        LongestSquareStreak lss = new LongestSquareStreak();
        int[] nums = {4, 3, 6, 16, 8, 2};
        System.out.println(lss.longestSquareStreak(nums));  // Output: 3
    }
}
 

Ejemplo Explicativo

Considera el ejemplo nums = [4,3,6,16,8,2] y la subsecuencia [4,16,2] cumple con las condiciones de racha de cuadrados después de ser ordenada. Por lo tanto, la longitud de la racha de cuadrados más larga es 3.

Conclusión

Implementar la solución en Java proporciona una manera eficiente de abordar el problema de la longitud de la racha de cuadrados más larga en un array. Aprovechar estructuras como HashSet y técnicas de búsqueda eficaz garantiza un rendimiento óptimo incluso para inputs grandes.