Given an infinite number line. You start at 0 and can go either to the left or to the right. The condition is that in the i^{th} move, youmust take i steps. Given a destination D , find the minimum number of steps required to reach that destination.
Example 1:
Input: D = 2
Output: 3
Explaination: The steps takn are +1, -2 and +3.
Example 2:
Input: D = 10
Output: 4
Explaination: The steps are +1, +2, +3 and +4.
Your Task:
You do not need to read input or print anything. Your task is to complete the function minSteps() which takes the value D as input parameter and returns the minimum number of steps required to reach the dedstination D from 0.
Expected Time Complexity: O(D)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ D ≤ 10000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Complete search

Starter code: #User function Template for python3

class Solution:
    def minSteps(self, D):
        # code here

Solutions:
class Solution:

	def minSteps(self, D):
		(steps, curr) = (0, 0)
		while curr < D:
			steps += 1
			curr += steps
		while curr - D & 1:
			steps += 1
			curr += steps
		return steps


class Solution:

	def minSteps(self, d):
		s = 0
		c = 0
		while s < d:
			s += c
			c += 1
		while (s - d) % 2 != 0:
			s += c
			c += 1
		return c - 1


class Solution:

	def minSteps(self, tar):
		sum = 0
		steps = 0
		while sum < tar:
			sum += steps
			steps += 1
		while (sum - tar) % 2:
			sum += steps
			steps += 1
		return steps - 1


class Solution:

	def minSteps(self, target):
		target = abs(target)
		k = 0
		while target > 0:
			k += 1
			target -= k
		return k if target % 2 == 0 else k + 1 + k % 2


class Solution:

	def minSteps(self, D):
		setti = set([0])
		i = 0
		while D not in setti:
			temp = set()
			i += 1
			for item in setti:
				temp.add(item - i)
				temp.add(item + i)
			setti = temp
		return i


class Solution:

	def minSteps(self, D):
		if D == 0 or D == 1:
			return D
		sum = 0
		count = 1
		while 1:
			sum += count
			if sum == D:
				return count
			if sum > D and (sum - D) % 2 == 0:
				return count
			count += 1


from collections import deque

class Solution:

	def minSteps(self, D):
		curr = 0
		step = 1
		while True:
			curr += step
			if curr == D:
				break
			elif curr > D and (D - curr) % 2 == 0:
				break
			step += 1
		return step


class Solution:

	def minSteps(self, target):
		steps = 0
		source = 0
		target = abs(target)
		while source < target:
			steps += 1
			source += steps
		while (source - target) % 2 != 0:
			steps += 1
			source += steps
		return steps


class Solution:

	def minSteps(self, D):
		r = 0
		i = 0
		while True:
			i += 1
			r += i
			if D == r or (r > D and (r - D) % 2 == 0):
				break
		return i


class Solution:

	def minSteps(self, D):
		positions = set([0])
		mv = 0
		while D not in positions:
			mv += 1
			nxt = []
			for i in positions:
				nxt.append(i + mv)
				nxt.append(i - mv)
			positions = set(nxt)
		return mv


class Solution:

	def minSteps(self, d):
		summ = 0
		steps = 0
		while summ < d or (summ - d) % 2 == 1:
			steps += 1
			summ += steps
		return steps


class Solution:

	def minSteps(self, D):
		target = abs(D)
		sum = 0
		step = 0
		while sum < target or (sum - target) % 2 != 0:
			step += 1
			sum += step
		return step


class Solution:

	def solve(self, i, D, st, dp):
		if abs(i) > D:
			return 100000000
		if i == D:
			return 0
		if (i, st) in dp:
			return dp[i, st]
		left = self.solve(i - st, D, st + 1, dp)
		right = self.solve(i + st, D, st + 1, dp)
		dp[i, st] = 1 + min(left, right)
		return dp[i, st]

	def minSteps(self, D):
		step = 0
		sumi = 0
		while sumi < D:
			sumi += step
			step += 1
		while (sumi - D) % 2:
			sumi += step
			step += 1
		return step - 1
		dp = {}
		return self.solve(0, D, 1, dp)


import sys

class Solution:

	def minSteps(self, D):
		i = 1
		while True:
			if i == D:
				return i
			if i > D:
				if (i - D) % 2 == 0:
					return i
				elif i % 2 == 0:
					return i + 1
				else:
					return i + 2
			D -= i
			i += 1


class Solution:

	def minSteps(self, D):
		D = abs(D)
		s = 0
		i = 1
		while s < D:
			s += i
			i += 1
		i -= 1
		if s == D:
			return i
		while 1:
			if (s + D) % 2 == 0:
				return i
			i += 1
			s += i


class Solution:

	def minSteps(self, des):
		step = 0
		sm = 0
		while sm < des or (sm - des) % 2 == 1:
			step += 1
			sm += step
		return step


class Solution:

	def minSteps(self, n):
		i = 1
		sm = 0
		while sm != n:
			sm += i
			if sm == n:
				return i
			if sm > n:
				if (sm - n) % 2 == 0:
					return i
			i += 1
		if sm == n:
			return i


class Solution:

	def minSteps(self, D):
		i = 0
		step = 0
		while i < D or (i - D) % 2 != 0:
			step += 1
			i += step
		return step


class Solution:

	def minSteps(self, D):

		def rec(D, curr=0, i=1):
			if curr < D:
				return rec(D, curr + i, i + 1)
			if (curr - D) % 2:
				return rec(D, curr + i, i + 1)
			return i - 1
		return rec(D)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		D = int(input())
		ob = Solution()
		print(ob.minSteps(D))


class Solution:

	def minSteps(self, D):

		def rec(sum, step, D):
			if sum >= D and (sum - D) % 2 == 0:
				return step
			step = step + 1
			sum = sum + step
			return rec(sum, step, D)
		return rec(0, 0, D)


class Solution:

	def minSteps(self, D):
		i = 1
		sum = 0
		while True:
			sum += i
			if sum == D:
				return i
			if sum > D:
				if (sum - D) % 2 == 0:
					return i
				elif i % 2 != 0:
					return i + 2
				else:
					return i + 1
			i += 1


import math

class Solution:

	def minSteps(self, D):
		x = abs(D)
		i = int(math.sqrt(x))
		pos = i * (i + 1) // 2
		cnt = i
		i += 1
		while pos < x:
			pos += i
			cnt += 1
			i += 1
		d = pos - x
		if d % 2 == 1:
			if cnt % 2 == 0:
				cnt += 1
			else:
				cnt += 2
		return cnt


from collections import defaultdict

class Solution:

	def minSteps(self, D):
		steps = 0
		sum = 0
		while True:
			sum += steps
			if sum == D or (sum > D and (sum - D) % 2 == 0):
				return steps
			steps += 1
		return 0


from collections import deque

class Solution:

	def minSteps(self, target):
		k = 0
		while target > 0:
			k += 1
			target -= k
		if target % 2 == 0:
			return k
		elif k % 2 == 0:
			return k + 1
		else:
			return k + 2


import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def recur(self, s, d, i):
		global dp
		import sys
		key = str(s) + '-' + str(i)
		if abs(s) > d:
			return sys.maxsize
		if s == d:
			return 0
		if key in dp:
			return dp[key]
		l = 1 + self.recur(s + i, d, i + 1)
		r = 1 + self.recur(s - i, d, i + 1)
		dp[key] = min(l, r)
		return dp[key]

	def minSteps(self, d):
		global dp
		dp = {}
		d = abs(d)
		sum = 0
		step = 0
		while sum < d or (sum - d) % 2 != 0:
			step = step + 1
			sum = sum + step
		return step


class Solution:

	def minSteps(self, D):
		n = 0
		s = 0
		while s < D:
			s += n
			n += 1
		n -= 1
		d = s - D
		if d % 2 == 0:
			return n
		elif n % 2 == 0:
			return n + 1
		else:
			return n + 2


class Solution:

	def minSteps(self, D):
		d = abs(D)
		cpos = 0
		move_no = 1
		steps = 0
		while cpos < d:
			cpos += move_no
			move_no += 1
			steps += 1
		if cpos == d:
			return steps
		else:
			diff = cpos - d
			if diff % 2 == 0:
				return steps
			elif move_no % 2 == 1:
				return steps + 1
			else:
				return steps + 2


class Solution:

	def minSteps(self, D):
		steps = 0
		sumn = 0
		while sumn < D:
			sumn += steps
			steps += 1
		while (sumn - D) % 2:
			sumn += steps
			steps += 1
		return steps - 1


class Solution:

	def minSteps(self, target):
		if target == 0:
			return 0
		ans = 0
		steps = 0
		target = abs(target)
		while ans < target:
			ans += steps
			steps += 1
		while (ans - target) % 2 == 1:
			ans += steps
			steps += 1
		return steps - 1


class Solution:

	def minSteps(self, D):
		steps = 0
		s = 0
		while True:
			s += steps
			steps += 1
			if s == D:
				return steps - 1
				break
			if s > D and (s - D) % 2 == 0:
				return steps - 1
				break


import collections

def dictHelper():
	return False

def steps(source, step, dest):
	if abs(source) > dest:
		return sys.maxsize
	if source == dest:
		return step
	pos = steps(source + step + 1, step + 1, dest)
	neg = steps(source - step - 1, step + 1, dest)
	return min(pos, neg)

class Solution:

	def minSteps(self, D):
		steps = 0
		D = abs(D)
		curr_sum = 0
		while curr_sum != D:
			if curr_sum < D:
				steps += 1
				curr_sum = curr_sum + steps
			if curr_sum > D:
				diff = curr_sum - D
				if diff % 2 == 0:
					break
				else:
					steps += 1
					curr_sum = curr_sum + steps
		return steps


import sys

def steps(source, step, dest):
	if abs(source) > dest:
		return sys.maxsize
	if source == dest:
		return step
	pos = steps(source + step + 1, step + 1, dest)
	neg = steps(source - step - 1, step + 1, dest)
	return min(pos, neg)

class Solution:

	def minSteps(self, D):
		i = 1
		while True:
			if i == D:
				return i
			if i > D:
				if (i - D) % 2 == 0:
					return i
				elif i % 2 == 0:
					return i + 1
				else:
					return i + 2
			D -= i
			i += 1


class Solution:

	def minSteps(self, D):
		D = abs(D)
		if D == 0:
			return 0
		currsum = 0
		steps = 0
		i = 1
		while currsum < D:
			currsum += i
			i += 1
			steps += 1
		if currsum == D:
			return steps
		while (currsum - D) % 2 != 0:
			currsum += i
			i += 1
			steps += 1
		return steps


import math

class Solution:

	def minSteps(self, D):
		target = D
		target = abs(target)
		k = 0
		while target > 0:
			k += 1
			target -= k
		return k if target % 2 == 0 else k + 1 + k % 2


class Solution:

	def minSteps(self, D):
		(step, sum) = (0, 0)
		while sum < D:
			sum += step
			step += 1
		while (sum - D) % 2:
			sum += step
			step += 1
		return step - 1


class Solution:

	def minSteps(self, target):
		s = 0
		i = 0
		while s < target:
			s += i
			i += 1
		while (s - target) % 2 == 1:
			s += i
			i += 1
		return i - 1


class Solution:

	def minSteps(self, D):
		N = int(((1 + 8 * D) ** 0.5 - 1) / 2)
		L = N * (N + 1) // 2
		if L == D:
			return N
		if (L + N + 1 - D) % 2 == 0:
			return N + 1
		return N + 3 - N % 2


class Solution:

	def minSteps(self, D):
		if D == 1:
			return 1
		n = 1
		while n:
			z = n * (n - 1) // 2
			if z - D >= 0 and (z - D) % 2 == 0:
				return n - 1
			n += 1
		return 0


class Solution:

	def minSteps(self, target):
		(steps, Sum) = (0, 0)
		while Sum < target:
			Sum += steps
			steps += 1
		while (Sum - target) % 2 == 1:
			Sum += steps
			steps += 1
		return steps - 1


import math

class Solution:

	def minSteps(self, target):
		t = abs(target)
		n = math.floor(math.sqrt(2 * t))
		while True:
			to_minus = (n + 1) * n / 2 - t
			if to_minus >= 0:
				if to_minus % 2 == 0:
					return int(n)
			n += 1


class Solution:

	def minSteps(self, D):
		(steps, summ) = (0, 0)
		while True:
			summ += steps
			steps += 1
			if summ == D:
				return steps - 1
			if summ > D and (summ - D) % 2 == 0:
				return steps - 1


class Solution:

	def minSteps(self, D):
		count = 1
		n = 1
		sum = 0
		while sum != D:
			sum += n
			if sum == D:
				return n
			if sum > D:
				if (sum - D) % 2 == 0:
					return n
			n += 1


class Solution:

	def minSteps(self, D):
		(ans, k) = (0, 0)
		D = abs(D)
		while ans < D:
			ans += k
			k += 1
		while (ans - D) % 2 == 1:
			ans += k
			k += 1
		return k - 1


class Solution:

	def minSteps(self, D):
		(ans, sum) = (0, 0)
		while 1:
			sum += ans
			ans += 1
			if sum == D:
				return ans - 1
			if sum > D and (sum - D) % 2 == 0:
				return ans - 1
		return 0


class Solution:

	def minSteps(self, D):
		sm = 0
		st = 1
		while True:
			sm += st
			if sm == D:
				return st
			if sm > D and (sm - D) % 2 == 0:
				return st
			st += 1


import math

class Solution:

	def minSteps(self, target):
		target = abs(target)
		n = math.ceil(math.sqrt(2 * target) - 1)
		while True:
			upper = n * (n + 1) // 2
			if upper >= target and (upper - target) % 2 == 0:
				break
			n += 1
		return n


class Solution:

	def minSteps(self, n):
		steps = 0
		source = 0
		while source < n:
			steps += 1
			source += steps
		if source == n or (source - n) % 2 == 0:
			return steps
		while (n - source) % 2 != 0:
			steps += 1
			source += steps
		return steps


class Solution:

	def minSteps(self, D):
		currpos = 0
		move = 0
		while currpos < D:
			currpos += move
			move += 1
		while (currpos - D) % 2:
			currpos += move
			move += 1
		return move - 1


class Solution:

	def minSteps(self, D):
		t = 0
		if D == 1:
			return 1
		for i in range(1, D * D):
			t += i
			if t == D:
				return i
			if t > D:
				if (t - D) % 2 == 0:
					return i