Correct Gp DSA Problem Solution

Posted by admin August 2, 2023
Correct Gp Even Numbers DSA Problem Solution
Correct Gp Even Numbers DSA Problem Solution

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

ai,

ai+1 …..

an−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

ai 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

Input

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

0≤N≤105) — the length of sequence that teaches gave to Rohan.

The second line of each test case contains N integers

ai,

ai+1 …..

an−1 (

0≤ai≤2∗104) — the sorted incorrect GP .

Output

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

Examples
Input
3
64 100 125
Output
64 80 100 125
Input
4
2 8 16 32
Output
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;
}