Given N Magnets which are placed linearly, with each magnet to be considered as of point object. Each magnet suffers force from its left sided magnets such that they repel it to the right and vice versa. All forces are repulsive. The force being equal to the inverse of the distance (1/d , d being the distance). Now given the positions of the magnets, the task to find all the points along the linear line where net force is ZERO. 
More Formally, Magnets are placed on X axis, the coordinates of which are given, you are asked to find out the X-co-ordinates of all the equilibrium points (i.e. the point where net force is zero). You notice the point each magnet repels each other, it means the polarity of the magnet is such that exerts +ve force in its right side and -ve force in left side, (here +ve is considered in +ve direction of x-axis). And that forces are inversely proportional to the distance, thus there lies an equilibrium point between every two magnetic points. Thus there will be total of N-1 equllibrium points. You have to find those N-1 points.
Note: Array M[] is sorted and distance have to be calculated with precision of 2 decimal places.
 
Example 1:
Input:
N = 2
M[] = {1, 2}
Output:
1.50
Explanation:
The mid point of two points will have 
net force zero, thus answer = 1.50
 
Example 2:
Input:
N = 4
M[] = {0, 10, 20, 30}
Output:
3.82, 15.00, 26.18
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function nullPoints() which takes the array M[], its size N as inputs and an answer array getAnswer[] to store the points having net force zero till precised two decimal places.
Expected Time Complexity: O(N^{2} * Log(N))
Expected Auxiliary Space: O(1)
 
Constraints:
2 ≤ N ≤ 10^{5}
0 ≤  M[1] < ....M[i] < M[i+1] < ....M[N] ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Mathematics

Complete search

Starter code: #User function Template for python3



class Solution:

    def nullPoints(self, n, a, getAnswer):

        # Your code goes here 





Solutions:
class Solution:

	def nullPoints(self, n, a, getAnswer):
		z = 0
		for i in range(n - 1):
			start = a[i]
			end = a[i + 1]
			while True:
				mid = (start + end) / 2
				eq = self.equilibrium(a, mid)
				if eq > 0:
					start = mid
				elif eq < 0:
					end = mid
				else:
					getAnswer[i] = mid
					break

	def equilibrium(self, a, mid):
		ans = 0
		for i in range(len(a)):
			if mid - a[i] != 0:
				ans = ans + 1 / (mid - a[i])
		return round(ans, 5)


class Solution:

	def calc(self, a, n, mid):
		ans = 0
		for i in range(n):
			if a[i] < mid:
				ans += 1 / (mid - a[i])
			else:
				ans -= 1 / (a[i] - mid)
		return ans

	def search(self, a, i, n):
		(lo, hi) = (a[i], a[i + 1])
		while hi - lo > 1e-06:
			mid = (lo + hi) / 2
			v = self.calc(a, n, mid)
			if v > 0:
				lo = mid
			else:
				hi = mid
		return lo

	def nullPoints(self, n, a, getAnswer):
		for i in range(n - 1):
			getAnswer[i] = self.search(a, i, n)


class Solution:

	def nullPoints(self, n, a, getAnswer):
		for i in range(n - 1):
			lo = a[i]
			hi = a[i + 1]
			while round(lo, 2) != round(hi, 2):
				mid = (lo + hi) / 2
				force = sum((1 / (x - mid) for x in a))
				if force == 0:
					lo = mid
					break
				elif force < 0:
					lo = mid
				else:
					hi = mid
			getAnswer[i] = round(mid, 2)


class Solution:

	def nullPoints(self, n, a, getAnswer):

		def f(l, h, a, n):
			while l < h:
				mid = (l + h) / 2
				F = 0
				for i in range(n):
					F += 1 / (mid - a[i])
				if F > 1e-06:
					l = mid
				elif F < -1e-06:
					h = mid
				else:
					return mid
		for i in range(n - 1):
			getAnswer[i] = f(a[i], a[i + 1], a, n)


class Solution:

	def nullPoints(self, n, a, getAnswer):
		z = 0
		for i in range(n - 1):
			left = a[i]
			right = a[i + 1]
			while True:
				mid = (left + right) / 2
				equation = self.equilibrium(a, mid)
				if equation > 0:
					left = mid
				elif equation < 0:
					right = mid
				else:
					getAnswer[i] = mid
					break

	def equilibrium(self, a, mid):
		ans = 0
		for i in range(len(a)):
			if mid - a[i] != 0:
				ans = ans + 1 / (mid - a[i])
		return round(ans, 5)


class Solution:

	def nullPoints(self, n, a, getAnswer):
		z = 0
		for i in range(n - 1):
			start = a[i]
			end = a[i + 1]
			while True:
				mid = (start + end) / 2
				eq = self.equilibrium(a, mid)
				if eq > 0:
					start = mid
				elif eq < 0:
					end = mid
				else:
					getAnswer[i] = mid
					break

	def equilibrium(self, a, mid):
		ans = 0
		for i in range(len(a)):
			if mid - a[i] != 0:
				ans = ans + 1 / (mid - a[i])
		return round(ans, 5)

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		getAnswer = [0] * n
		ob = Solution()
		ob.nullPoints(n, a, getAnswer)
		for i in range(0, n - 1):
			print('{:.2f}'.format(getAnswer[i]), end=' ')
		print()
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def nullPoints(self, n, a, getAnswer):
		res = []

		def check(low, high, a):
			while low <= high:
				mid = (low + high) / 2
				ans = force = 0
				for i in range(n):
					force += 1 / (mid - a[i])
				if abs(force) < 1e-06:
					return mid
				elif force < 0:
					high = mid
				else:
					low = mid
			return low
		for i in range(n - 1):
			x = round(check(a[i], a[i + 1], a), 2)
			getAnswer[i] = x

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		getAnswer = [0] * n
		ob = Solution()
		ob.nullPoints(n, a, getAnswer)
		for i in range(0, n - 1):
			print('{:.2f}'.format(getAnswer[i]), end=' ')
		print()
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def equi(self, low, high, magnet, n):
		while low < high:
			mid = (low + high) / 2
			tf = 0
			for i in range(n):
				tf += 1 / (mid - magnet[i])
			if abs(tf) < 1e-06:
				return mid
			elif tf < 0:
				high = mid
			else:
				low = mid
		return low

	def nullPoints(self, n, a, getAnswer):
		for i in range(n - 1):
			getAnswer[i] = self.equi(a[i], a[i + 1], a, n)

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		getAnswer = [0] * n
		ob = Solution()
		ob.nullPoints(n, a, getAnswer)
		for i in range(0, n - 1):
			print('{:.2f}'.format(getAnswer[i]), end=' ')
		print()
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def calculateForce(self, a, point):
		force = 0
		for i in a:
			force += 1 / (i - point)
		return round(force, 5)

	def nullPoints(self, n, a, getAnswer):
		for i in range(n - 1):
			low = a[i]
			high = a[i + 1]
			while low <= high:
				mid = (low + high) / 2
				net_force = self.calculateForce(a, mid)
				if net_force == 0:
					getAnswer[i] = mid
					break
				if net_force < 0:
					low = mid
				else:
					high = mid


class Solution:

	def helper(self, a, mid):
		ans = 0
		for i in range(len(a)):
			if mid - a[i] != 0:
				ans = ans + 1 / (mid - a[i])
		return round(ans, 5)

	def nullPoints(self, n, a, getAnswer):
		for i in range(n - 1):
			s = a[i]
			e = a[i + 1]
			while s < e:
				mid = (s + e) / 2
				eq = 0
				for j in a:
					if mid - j != 0:
						eq += 1 / (mid - j)
				eq = round(eq, 5)
				if eq > 0:
					s = mid
				elif eq < 0:
					e = mid
				else:
					getAnswer[i] = mid
					break


class Solution:

	def nullPoints(self, n, m, getAnswer):
		for i in range(1, n):
			low = m[i - 1]
			high = m[i]
			while 1:
				mid = (low + high) / 2
				force = 0
				for k in range(n):
					if m[k] != mid:
						force = force + 1 / (m[k] - mid)
				force = round(force, 6)
				if force > 0:
					high = mid
				elif force < 0:
					low = mid
				else:
					getAnswer[i - 1] = mid
					break
		return


import math

class Solution:

	def nullPoints(self, n, a, getAnswer):
		for j in range(n - 1):
			l = a[j]
			h = a[j + 1]
			while True:
				mid = (l + h) / 2
				f = 0
				for i in range(n):
					if mid - a[i] != 0:
						f = f + 1 / (mid - a[i])
				f = round(f, 5)
				if f < 0:
					h = mid
				elif f > 0:
					l = mid
				else:
					getAnswer[j] = mid
					break
		return getAnswer


class Solution:

	def nullPoints(self, n, a, getAnswer):
		for i in range(n - 1):
			low = a[i]
			high = a[i + 1]
			while round(low, 2) != round(high, 2):
				mid = (low + high) / 2
				f = sum((1 / (x - mid) for x in a))
				if f == 0:
					low = mid
					break
				elif f < 0:
					low = mid
				else:
					high = mid
			getAnswer[i] = round(low, 2)
		return getAnswer


def search(lo, hi, a, n):
	mid = (lo + hi) / 2
	dis = 0
	for i in range(n):
		dis += 1 / (mid - a[i])
	if abs(dis) < 1e-12:
		return mid
	if dis > 0:
		return search(mid, hi, a, n)
	else:
		return search(lo, mid, a, n)

class Solution:

	def nullPoints(self, n, a, ans):
		for i in range(n - 1):
			ans[i] = search(a[i], a[i + 1], a, n)


class Solution:

	def nullPoints(self, n, a, getAnswer):
		delta = 0.0001
		for i in range(n - 1):
			low = a[i]
			high = a[i + 1]
			while True:
				mid = (low + high) / 2
				net_force = self.net_force(a, mid)
				if net_force > 0:
					low = mid
				elif net_force < 0:
					high = mid
				else:
					getAnswer[i] = mid
					break
		return getAnswer

	def net_force(self, M, x):
		total = 0
		for m in M:
			if x - m != 0:
				total = total + 1 / (x - m)
		return round(total, 5)


class Solution:

	def nullPoints(self, n, a, getAnswer):

		def neutralPoint(low, high, magnets, n):
			while low < high:
				mid = (low + high) / 2
				totalForce = 0
				for i in range(n):
					totalForce += 1 / (mid - magnets[i])
				if abs(totalForce) < 1e-06:
					return mid
				if totalForce < 0:
					high = mid
				else:
					low = mid
		for i in range(n):
			if i < n - 1:
				getAnswer[i] = neutralPoint(a[i], a[i + 1], a, n)
		return getAnswer


class Solution:

	def nullPoints(self, n, a, getAnswer):

		def bs(a, start, end, mid):
			ans = 0
			for i in range(n):
				if mid - a[i] != 0:
					ans += 1 / (mid - a[i])
			return round(ans, 5)
		for i in range(n - 1):
			start = a[i]
			end = a[i + 1]
			while True:
				mid = (start + end) / 2
				point = bs(a, start, end, mid)
				if point < 0:
					end = mid
				elif point > 0:
					start = mid
				else:
					getAnswer[i] = mid
					break


class Solution:

	def print(self, *args):
		pass

	def nullPoints(self, n, a, getAnswer):
		for i in range(n - 1):
			fValue = i
			bComplete = False
			iTryCounter = 0
			iXLeft = a[i]
			iXRight = a[i + 1]
			iXMid = (iXLeft + iXRight) / 2
			while bComplete == False:
				iTryCounter += 1
				if iTryCounter > 20:
					getAnswer[i] = iXMid
					bComplete = True
				iXMid = (iXLeft + iXRight) / 2
				self.print('l m r', iXLeft, iXMid, iXRight)
				iResultLeft = 0
				iResultRight = 0
				for l in range(0, i + 1):
					iResultLeft += 1 / (iXMid - a[l])
				for r in range(i + 1, n):
					iResultRight += 1 / (a[r] - iXMid)
				iResultDiff = iResultRight - iResultLeft
				self.print('res l r diff', iResultLeft, iResultRight, iResultDiff)
				fDiffMin = 5e-06
				if abs(iResultDiff) < fDiffMin:
					self.print('abs iResultDiff < fDiffMin', fDiffMin, iResultDiff)
					getAnswer[i] = iXMid
					bComplete = True
				elif iResultDiff < 0:
					iXLeft = iXMid
				else:
					iXRight = iXMid
				self.print('end comp l m r', bComplete, iXLeft, iXMid, iXRight)
			self.print(getAnswer)


from math import inf, isclose

def calc(a, n, m):
	f = 0
	for i in range(n):
		if a[i] < m:
			f += 1 / (m - a[i])
		elif a[i] > m:
			f += -1 / (a[i] - m)
		else:
			pass
	return f

def find(a, n, l, r):
	while True:
		m = (l + r) / 2
		v = calc(a, n, m)
		if isclose(v, 0, rel_tol=0, abs_tol=1e-07):
			return m
		if v > 0:
			l = m
		elif v < 0:
			r = m

class Solution:

	def nullPoints(self, n, a, ans):
		for i in range(n - 1):
			eqp = find(a, n, a[i], a[i + 1])
			ans[i] = eqp
		return ans


class Solution:

	def nullPoints(self, n, a, getAnswer):
		for i in range(n - 1):
			start = a[i]
			end = a[i + 1]
			while True:
				mid = (start + end) / 2
				f = self.force(a, mid)
				if f > 0:
					start = mid
				elif f < 0:
					end = mid
				else:
					getAnswer[i] = mid
					break

	def force(self, a, mid):
		forc = 0
		for j in range(len(a)):
			if mid != a[j]:
				forc = forc + 1 / (mid - a[j])
		return round(forc, 5)


class Solution:

	def nullPoints(self, n, a, getAnswer):
		arr = []

		def eq(num):
			ans = 0
			for i in a:
				if i < num:
					ans += 1 / (num - i)
				else:
					ans -= 1 / (i - num)
			return ans
		for i in range(1, n):
			(low, high) = (a[i - 1], a[i])
			while low < high:
				mid = (low + high) / 2
				temp = eq(mid)
				if abs(temp) < 1e-06:
					break
				elif temp < 0:
					high = mid
				else:
					low = mid
			getAnswer[i - 1] = mid


class Solution:

	def nullPoints(self, n, a, getAnswer):
		for i in range(n - 1):
			start = a[i]
			end = a[i + 1]
			while start <= end:
				mid = (start + end) / 2
				eqb = self.equilbrium(a, mid)
				if eqb > 0:
					start = mid
				elif eqb < 0:
					end = mid
				else:
					getAnswer[i] = mid
					break

	def equilbrium(self, a, mid):
		force = 0
		for i in range(len(a)):
			if mid - a[i] != 0:
				force += 1 / (mid - a[i])
		return round(force, 5)


class Solution:

	def sigmaForce(self, x, a):
		netForce = 0
		for i in a:
			netForce += 1 / (x - i)
		return netForce

	def bs(self, l, r, a):
		while r - l >= 1e-06:
			x = l + (r - l) / 2
			netForce = self.sigmaForce(x, a)
			if netForce > 0:
				l = x
			else:
				r = x
		return r

	def nullPoints(self, n, a, getAnswer):
		points = []
		for i in range(len(a) - 1):
			(l, r) = (a[i], a[i + 1])
			getAnswer[i] = self.bs(l, r, a)
		return points


class Solution:

	def equi(self, a, mid):
		ans = 0
		for i in range(len(a)):
			if mid - a[i] != 0:
				ans += 1 / (mid - a[i])
		return round(ans, 10)

	def nullPoints(self, n, a, getAnswer):
		for i in range(n - 1):
			start = a[i]
			end = a[i + 1]
			while True:
				mid = (end + start) / 2
				equili = self.equi(a, mid)
				if equili > 0:
					start = mid
				elif equili < 0:
					end = mid
				else:
					getAnswer[i] = mid
					break


import sys
sys.setrecursionlimit(10 ** 5)

class Solution:

	def bin_search(self, s, e, l, r, a):
		if abs(s - e) >= 1e-06:
			mid = (e + s) / 2
			lp = rp = 0
			for i in range(l):
				lp += 1 / abs(a[i] - mid)
			for i in range(l, r):
				rp += 1 / abs(a[i] - mid)
			if abs(lp - rp) <= 1e-06:
				return mid
			if lp < rp:
				return self.bin_search(s, mid, l, r, a)
			else:
				return self.bin_search(mid, e, l, r, a)
		return s

	def nullPoints(self, n, a, getAnswer):
		for i in range(1, n):
			getAnswer[i - 1] = self.bin_search(a[i - 1], a[i], i, n, a)
		return getAnswer


class Solution:

	def nullPoints(self, n, a, getAnswer):
		for i in range(0, n - 1):
			getAnswer[i] = self.check(a, n, a[i], a[i + 1])

	def check(self, a, n, low, hig):
		while low <= hig:
			mid = (hig + low) / 2
			force = 0
			for i in range(n):
				force += 1 / (mid - a[i])
			if abs(force) < 1e-06:
				return mid
			elif force > 0:
				low = mid
			else:
				hig = mid
		return low


class Solution:

	def nullPoints(self, n, l, ans):

		def fun(i, j):
			while i < j:
				mid = (i + j) / 2
				c = 0
				for k in range(n):
					c += 1 / (l[k] - mid)
				if abs(c) <= 1e-06:
					return round(mid, 2)
				if c > 0:
					j = mid
				else:
					i = mid
			return i
		for k in range(n - 1):
			ans[k] = fun(l[k], l[k + 1])


class Solution:

	def solve(self, a, n, low, high):
		while low < high:
			mid = (low + high) / 2
			force = 0
			for i in range(n):
				force += 1 / (mid - a[i])
			force = round(force, 5)
			if abs(force) < 1e-06:
				return round(mid, 2)
			if force > 0:
				low = mid
			else:
				high = mid
		return round(low, 2)

	def nullPoints(self, n, a, getAnswer):
		for i in range(n - 1):
			getAnswer[i] = self.solve(a, n, a[i], a[i + 1])


class Solution:

	def nullPoints(self, n, a, getAnswer):

		def left(i, m):
			f = 0
			for j in range(i, n):
				f += 1 / (a[j] - m)
			return f

		def right(i, m):
			f = 0
			for j in range(i - 1, -1, -1):
				f += 1 / (m - a[j])
			return f
		for i in range(n - 1):
			(l, r) = (a[i], a[i + 1])
			while l <= r:
				m = (l + r) / 2
				(f1, f2) = (left(i, m), right(i, m))
				if abs(f1 - f2) < 1e-06:
					break
				elif f1 < f2:
					l = m
				else:
					r = m
			getAnswer[i] = m


GREATER = 1
SMALLER = 2
EQUAL = 3

def check(x, i, a, n):
	t1 = 0
	t2 = 0
	for j in range(0, i + 1):
		if x == a[j]:
			return GREATER
		t1 += 1 / (x - a[j])
	for j in range(i + 1, n):
		if x == a[j]:
			return LESSER
		t2 += 1 / (a[j] - x)
	if t1 == t2:
		return EQUAL
	return GREATER if t1 > t2 else SMALLER

class Solution:

	def nullPoints(self, n, a, getAnswer):
		for i in range(n - 1):
			p = a[i]
			q = a[i + 1]
			while round(p, 2) != round(q, 2):
				mid = (p + q) / 2
				check_mid = check(mid, i, a, n)
				if check_mid == EQUAL:
					break
				if check_mid == SMALLER:
					q = mid
				else:
					p = mid
			getAnswer[i] = round(mid, 2)


def search(l, h, a, n):
	mid = (l + h) / 2
	d = 0
	for i in range(n):
		d += 1 / (mid - a[i])
	if abs(d) < 1e-07:
		return mid
	if d > 0:
		return search(mid, h, a, n)
	else:
		return search(l, mid, a, n)

class Solution:

	def nullPoints(self, n, a, getAnswer):
		for i in range(n - 1):
			p = search(a[i], a[i + 1], a, n)
			getAnswer[i] = p


class Solution:

	def nullPoints(self, N, M, getAnswer):
		res = []

		def BinSearch(left, right, min_val, max_val):
			distance = (min_val + max_val) / 2
			left_res = sum([1 / abs(distance - point) for point in left])
			right_res = sum([1 / abs(point - distance) for point in right])
			end_force = left_res - right_res
			if -1e-06 < end_force < 1e-06:
				return distance
			elif end_force < 0:
				return BinSearch(left, right, min_val, distance)
			return BinSearch(left, right, distance, max_val)
		for ind in range(1, N):
			left = M[:ind]
			right = M[ind:]
			getAnswer[ind - 1] = float('{:.2f}'.format(BinSearch(left, right, M[ind - 1], M[ind])))
		return getAnswer


class Solution:

	def nullPoints(self, n, a, getAnswer):

		def sol(i, j, a, n):
			l = a[i]
			r = a[j]
			left = l
			right = r
			while right - left >= 1e-06:
				fl = 0
				fr = 0
				m = (left + right) / 2
				for k in range(n):
					if k <= i:
						fr += 1 / (m - a[k])
					else:
						fl += 1 / (a[k] - m)
				if fl < fr:
					left = m
				else:
					right = m
			return left
		for i in range(n - 1):
			getAnswer[i] = sol(i, i + 1, a, n)


class Solution:

	def nullPoints(self, n, a, ans):
		for i in range(n - 1):
			(fi, si) = (i, i + 1)
			(l, r) = (a[fi], a[si])
			while l < r:
				mid = (l + r) / 2
				force = sum((1 / (mid - v) for v in a if mid - v != 0))
				if abs(force) < 1e-07:
					ans[i] = mid
					break
				elif force < 0:
					r = mid
				else:
					l = mid