# PROBLEM LINK:

* Author:* Jaymeet Mehta

# DIFFICULTY:

EASY

# PREREQUISITES:

Simple observations , DP

# PROBLEM:

You are given an array A of N integers and Energy e, a special sequence is defined as [x,x*e,x*e^2,...,x*e^k] for any integer x and k. You have to find maximum length of such sequence among all sub sequences of A.

# QUICK EXPLANATION:

We can generate the hash table of the elements in the array and generate dp with 0 as initial value and the dp equation as dp[i]=dp[i/E]+1. and print the max value of dp

# EXPLANATION:

**Observation**

We can see that the special sequence is in the form of Geometric Progression with r=e.

So, We have to find the longest GP in the given Array.

**Logic**

As the sequence is in the form of GP, In GP we know that the G_i=G_{i-1}*r where G_i is the i^{th} term of GP.

We can use dp for this question. We can use the previous result to get the result of the current element of the array.

Let dp[x] be the answer maximum length of GP until element x.

So when we encounter x*e we can use dp[x] as a sub problem.

Then we have an easy solution,letâ€™s store dp in a map (unordered_map in c++) and initialize the map with the value 0 for every key.

dp[i]=dp[floor(i/E)]+1

Then the maximum element of dp will be our answer.

# TIME COMPLEXITY:

Time Complexity is O(N*logN) in average as the time of storing an element in a map is O(logN) in average.

# SOLUTIONS:

## Setter's Solution

```
#ILLUMINATI SEASON 6
'''
codechef id :mj_13
Problem : Jonesy Wants Help
'''
from collections import defaultdict
from sys import stdin,stdout
test=int(stdin.readline())
for _ in range(test):
N,E = map(int,stdin.readline().split())
A= [int(x) for x in stdin.readline().split()]
dp=defaultdict(int)
for i in A:
dp[i]=dp[i//E]+1
ans=max(list(dp.values()))
print(ans)
```