Summation of power K of absolute value of difference of every pair of array

Question

0.00/5 (No votes)

See more:

Basically f(x) is summation of power K of absolute value of difference of every pair of array.In this question n(number of element in array),k,and element will be given and i have to fine first absolute difference between every pair of array and raise its power k, then add all them and find the answer%pow(10,9)+7

What I have tried:

I tried this problem by using 3 loops , one for power. because value of k can be go till 100000,and element of array can be go till 10^9

Posted 5-Apr-20 7:56am

Member 14793179

Updated 6-Apr-20 11:02am

Add a Solution

Comments

k5054 5-Apr-20 14:31pm

Maybe you can post the exact problem you are trying to solve? As stated it would appear that you need to be able to calculate values in with a magnitude of the order of 1E+900000. That value is far too large for even a long double in 64 bits which would be of the order 1E+4932, so there must be some other constraints on the problem, OR you are expected to use a bignum library to compute the values.
That being said, you should also post your code. We are quite happy to review your solution and suggest fixes, but we don't provide solutions outright.

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

Member 14793221 · Answer 1 · 2020-04-05T08:37:00

Solution 1

trying to cheat uh (spider week of code NITT)

Posted 5-Apr-20 8:37am

Member 14793221

Member 14794342 · Answer 2 · 2020-04-06T11:02:00

Instead of using three loops with complexity O(n^3), you can use modular exponentiation as the third loop which will take O(log n) to compute power k for the difference of each pair of the array.
I want to add in this question how can we compute summation of differences of each pair raise to power k in less than O(n^2 log n).