In this post, we are going to solve Maths Equation DSA 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.
Maths Equation DSA Problem Statement
Ram is having a maths exam tomorrow but today he is stuck in a problem that was related to maths equations. So he needs your help to solve the equation. Below is the equation that Ram is facing a problem to solve.
Help Ram to solve this equation by finding the minimum value of X. You are given A, R, N or print -1 if no answer exists.
The first line of the test case contains a three integer A, R, N (
) — the integer value of the equation.
For each test case print the minimum value of X which satisfies the equation If no such solution exists print -1.
15 9 18
3
15 9 25
-1
Problem Solution in C++
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define mid(l, r) (l + (r - l) / 2)
#define int long long
#define mod 1000000007
constexpr int MOD = 998244353;
int EEA( int a, int b,int& x, int& y)
{
if (b == 0) {
x = 1;
y = 0;
return a;
}
else {
int x1, y1;
int gcd= EEA(b, a % b, x1, y1);
x = y1;
y = x1 - floor(a / b) * y1;
return gcd;
}
}
void linear_congruence(int A, int B, int N)
{
A = A % N;
B = B % N;
int u = 0, v = 0;
int d = EEA(A, N, u, v);
// No solution exists
if (B % d != 0)
{
cout << -1 << endl;
return;
}
int x0 = (u * (B / d)) % N;
if (x0 < 0)
x0 += N;
vector<int>ans;
for (int i = 0; i <= d - 1; i++)
ans.push_back( (x0 + i * (N / d)) % N);
sort(ans.begin(),ans.end());
cout<<ans[0]<<"\n";
}
int32_t main()
{
int a, b, n;
cin >> a >> b >> n;
linear_congruence(a, b, n);
}