A sequence a[0], a[1], …, a[N-1] is called decreasing if a[i] >= a[i+1] for each i: 0 <= i < N-1. You are given a sequence of numbers a[0], a[1],…, a[N-1] and a positive integer K. In each 'operation', you may subtract K from any element of the sequence. You are required to find the minimum number of 'operations' to make the given sequence decreasing.
Note: As the answer can be large return your answer modulo 10^{9}+7.
 
Example 1:
Input:
N = 4, K = 5
A[] = {1, 1, 2, 3}
Output:
3
Explanation:
One operation is required to change a[2] = 2
into -3 and two opertations are required to
change a[3] = 3 into -7. The resulting
sequence will be 1 1 -3 -7. Hence, in
total 3 operations are required.
 
Example 2:
Input:
N=5, K = 2
A[] = {5, 4, 3, 2, 1}
Output:
0
Explanation:
The sequence is already decreasing. Hence,
no operations are required in both the cases.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minMoves() which takes the array A[], its size N and an integer K as inputs and returns the minimum number of ‘operations’. Return your answer modulo 10^{9}+7.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{6}
1 <= K <= 100
-10^{6} <= a[] <= 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Mathematics

Starter code: #User function Template for python3

def minMoves( a, n, k):
    
    


Solutions:
import math

def minMoves(a, n, k):
	count = 0
	for i in range(1, n):
		if a[i] > a[i - 1]:
			diff = a[i] - a[i - 1]
			div = math.ceil(diff / k)
			count += div
			a[i] = a[i] - k * div
	return count % 1000000007


from math import ceil

def minMoves(a, n, k):
	output = []
	for i in range(n - 1):
		if a[i] < a[i + 1]:
			output.append(ceil((a[i + 1] - a[i]) / k))
			a[i + 1] -= output[-1] * k
	return sum(output) % (10 ** 9 + 7)


def minMoves(a, n, k):
	ans = 0
	for i in range(1, n):
		if a[i] > a[i - 1]:
			temp = a[i] - a[i - 1]
			ans += temp // k
			a[i] -= k * (temp // k)
			if temp % k != 0:
				ans += 1
				a[i] -= k
	return ans % 1000000007


def minMoves(a, n, k):
	re = 0
	dec = 0
	for i in range(0, len(a) - 1):
		if a[i] < a[i + 1]:
			s = a[i + 1] - a[i]
			if s % k == 0:
				re = s // k
			else:
				re = s // k + 1
			a[i + 1] = a[i + 1] - k * re
			dec += re
	return dec % (10 ** 9 + 7)


def minMoves(a, n, k):
	c = 0
	for i in range(n - 1):
		if a[i] >= a[i + 1]:
			continue
		else:
			if (a[i + 1] - a[i]) % k == 0:
				x = (a[i + 1] - a[i]) // k
				c += x
			else:
				x = (a[i + 1] - a[i]) // k + 1
				c = c + x
			a[i + 1] -= x * k
	return c % (10 ** 9 + 7)


def minMoves(a, n, k):
	mod = 10 ** 9 + 7
	moves = 0
	for i in range(1, n):
		if a[i] > a[i - 1]:
			change = (a[i] - a[i - 1] - 1) // k + 1
			moves += change
			moves = moves % mod
			a[i] = a[i] - k * change
	return moves % mod