15,035,685 members
1.00/5 (1 vote)
See more:
On solving a problem PRLCM:
SPOJ.com - Problem PRLCM[^]

I used O(n^2) algorithm
for 1sec I'm looking for some more efficient approach
I would be helpful if someone help out.

What I have tried:

C++
```#include <bits stdc++.h="">
#define ll long long int
#define f(i, a, b) for (us i = a; i < b; i++)
#define vi vector<us>
#define pb push_back
#define us unsigned long long int
#define endl '\n'
#define mod 998244353
#define mp make_pair
#define pi = 3.1415926535897932384626433
using namespace std;
us solve(us arr[], us);
us lcm(us, us);
us solve(us arr[], us n)
{
us sum = 0;

for (us i = 0; i < n - 1; i++)
{
for (us j = i + 1; j < n; j++)
{
sum = sum + lcm(arr[i], arr[j]);
}
sum = sum % mod;
}
return sum;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll t = 1;
while (t--)
{
us n;
cin >> n;
us arr[n];
for (us i = 0; i < n; i++)
cin >> arr[i];
cout << solve(arr, n);
}
return 0;
}

us lcm(us x, us y)
{
return ((x*y)/__gcd(x,y));
}```
Posted
Updated 13-Jul-20 7:26am
v2
Comments
Richard MacCutchan 13-Jul-20 10:54am

Remove the while loop, it serves no purpose.
Member 14849246 13-Jul-20 10:58am

ya! its a part of default competative code for multiple cases , other than that if you please help in algorithm like how to select all possible pairs and something like that
Richard MacCutchan 13-Jul-20 11:05am

Sorry, no idea, I stay well clear of those websites.

## Solution 1

The idea of problems like this is that you work out an efficient algorithm to solve it, learning in the process how to analyse a problem and evaluate viable solutions.

Us doing that part for you turns it into a straight "convert this to code" problem and that isn't the point at all - you learn nothing about anything useful.

Like Richard, I don't go near such sites - the problems are well away from the real-world problems I n3eed to solve so they are of no real interest to me: but read the question carefully, and come up with a few different ways to do it manually - then evaluate them for efficiency.

## Solution 2

Quote:
I used O(n^2) algorithm
for 1sec I'm looking for some more efficient approach

On first look, the problem is essentially O(N²), so optimizations are only marginally possible.
What is your problem with this code ?
Comments
Member 14849246 13-Jul-20 13:49pm

"constraints of the question"
it gives TLE on higher outputs

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Top Experts
Last 24hrsThis month
 OriginalGriff 128 Richard Deeming 60 Dave Kreskowiak 35 KarstenK 25 Richard MacCutchan 20
 OriginalGriff 2,955 Richard Deeming 1,783 Richard MacCutchan 1,590 CPallini 1,003 Dave Kreskowiak 731

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900