Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

akshatag0417's blog

By akshatag0417, history, 2 months ago, In English

Hi, this is my first blog. I came across this problem and wondered if it's a variation of a solved problem and needed help solving this.

  • Problem Statement:
  • Given an array of floats A, and a target sum k. You can do following things in one operation in the array:
  • 1) Pick any two integers from A, say A[i] and A[j] and calculate one of the following:
  • a) Linear Sum = A[i] + A[j]
  • b) Inverted Sum = (A[i] * A[j]) / (A[i] + A[j])
  • 2) Remove A[i] and A[j] from the array and add one the sums in to array. You cannot add both sums in the array, choose any one.

Error of 1e-6 is allowed while comparing calculated sum and the target sum

For Eg. Input : A = [1.0, 1.3, 1.5] , K = 5.0 Output: False

Input : A = [1.0, 1.3, 1.5] , K = 1.69 Output : True

Is it possible to solve this problem in polynomial time?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by akshatag0417 (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Additionally, if the output is false, can we print the closest value to this target sum?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by akshatag0417 (previous revision, new revision, compare).