Geometric Progression Subsequences Problem Statement

Given an array of ‘N’ integers, determine the number of subsequences of length 3 that form a geometric progression with a specified common ratio ‘R’.

Explanation:

A geometric progression (GP) or sequence is characterized by numbers that differ by a common ratio, such as 2, 4, 8, 16 with common ratio 2.

Note:

Return the answer modulo 109 + 7, as the result may be very large.

Input:

The first line contains an integer T denoting the number of test cases.
For each test case, the first line shows two integers N and R, the number of elements in the array and the common ratio.
The second line of each test case comprises N space-separated integers representing the array elements.

Output:

For each test case, print the number of subsequences of length 3 having the common ratio R.

Example:

Input:
T = 1
N = 4, R = 2
Array = [2, 4, 8, 16]
Output:
1

Constraints:

  • 1 <= T <= 50
  • 3 <= N <= 104
  • 1 <= R <= 104
  • 1 <= A[i] <= 109
  • Time Limit: 1 sec
AnswerBot
1d

Count the number of subsequences of length 3 forming a geometric progression with a specified common ratio in an array of integers.

  • Iterate through the array and for each element, check for possible su...read more

Help your peers!
Add answer anonymously...
Paytm Software Engineer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter