In this post, we are going to solve Correct GpDSA Problem from Tiktok Singapore, Online Assessments conducted on Septemeber,2022. Let’s have a look at the problem statement first and then try to solve the problem.

## Correct Gp DSA Problem Statement

Rohan hates maths and his teacher gives him a question related to Geometric Progression (GP). He was given an array of GP sequences which is

${a}_{i}$,

${a}_{i+1}$ …..

${a}_{n-1}$ but his teacher wants that Rohan to come up with the correct GP sequence. The only operation he is allowed to do is insert some elements

${a}_{i}$ for which the Gp ratio between every two consecutive elements became equally. If no solution exists print -1. Also, his teacher asked him to maximise the ratio of GP.

Now Rohan needs your help to find the correct GP sequence which has a maximum ratio

The first line of the test case contains a single integer N (

$0\le N\le {10}^{5}$) — the length of sequence that teaches gave to Rohan.

The second line of each test case contains N integers

${a}_{i}$,

${a}_{i+1}$ …..

${a}_{n-1}$ (

$0\le {a}_{i}\le 2\ast {10}^{4}$) — the sorted incorrect GP .

For each test case print the correct sequence of the array if it exists else print -1.

3 64 100 125

64 80 100 125

4 2 8 16 32

2 4 8 16 32

## Problem Solution in C++

```
#include<bits/stdc++.h>
using namespace std;
int n, a[200020];
vector<double> random_ratios;
int main() {
random_device rd;
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
assert(n > 2);
if (a[0] == a[n-1]) {
for (int i = 0; i < n; ++i) cout << a[i] << " ";
return 0;
}
random_ratios.push_back(a[1] * 1.0 / a[0]);
random_ratios.push_back(a[n-1] * 1.0 / a[n-2]);
for (int steps = 0; steps; ++steps) {
//std::default_random_engine generator;
uniform_int_distribution<int> yo(0, n-1);
int i = yo(gen);
int j = yo(gen);
if (i > j) swap(i, j);
double new_ratio = a[j] * 1.0 / a[i];
random_ratios.push_back(new_ratio);
}
for (auto ratio: random_ratios) {
set<double> mem;
double val = a[0];
while (val <= a[n-1]) {
mem.insert(val);
val = 1.0 * ratio * val;
}
int bulb = 1;
for (int i = 0; i < n; ++i) if (mem.count(a[i]) <= 0) {bulb = 0; break;}
if (bulb == 1) {
for (auto cc: mem) cout << cc << " ";
return 0;
}
}
cout << "-1";
return 0;
}
```

## Leave a Reply