Find longest subarray of given int array where each [i+1] element is square of [i]th element

Viewed 24

Hello I am solving following problem statement:

I have given int array with n elements. I need to find length of longest subarray where following condition is true for each element of that subArray: value[i]* value[i] = value[i+1] where [i] is index.

Example:

input = [16,4,9,3,2,32] 
output = 3

explanation: here there are two subarray where satisfy the condition [3,9] and [2,4,16]. So answer is [2,4,16] = 3

I have already written solution above. Is there any other way to solve this problem without nested for loop?

My coding:

public int solution(List<Integer> list) {
        if (list.size() <= 1)
            return -1;
        Collections.sort(list);
        int maxSubListSize = 0;
        for (int i = 0; i < list.size(); i++) {
            int value = list.get(i);
            int currentListSize = 0;
            for (int j = i + 1; j < list.size(); j++) {
                if (value * value == list.get(j)) {
                    value = list.get(j);
                    currentListSize++;
                }
            }
            maxSubListSize = Math.max(maxSubListSize, currentListSize == 0 ? 0 : currentListSize + 1);
        }
        System.out.println(maxSubListSize);
        return maxSubListSize == 0 ? -1 : maxSubListSize;
    }
0 Answers
Related