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
,
…..
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
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 (
) — the length of sequence that teaches gave to Rohan.
The second line of each test case contains N integers
,
…..
(
) — 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;
}