Ishaan is trapped in a city full of walls. To escape from there, it needs to climb N walls, one after the other. He can climb a wall if its height is atmost K.
Ishaan also has a superpower. He can reduce the height of a wall H by K by using his superpower. Since he can't use this power many times, calculate the minimum number of times he has to use this power to go over all the walls.
Example 1:
Ã¢â¬â¹Input : arr[ ] = {5, 3, 2, 6, 8} and K = 5
Output : 2
Explanation:
Heights : 5 3 2 6 8 Ishaan can climb a 
wall with height atmost 5. So he climbs 
the first 3 walls easily. Now he has to 
use his power to reduce the height of the 
4th wall. After using his power, heights 
: 5 3 2 1 8, Now to climb the last wall, 
he again uses his power. Final heights 
: 5 3 2 1 3
Ã¢â¬â¹Example 2:
Input : arr[ ] = {2, 6, 4, 8, 1, 6} and K = 4 
Output :  3 
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function ReducingWalls() that takes an array (arr), sizeOfArray (n), an integer K and return the minimum number of times he has to use this power to go over all the walls The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints :
1 ≤ N ≤ 10^{5}
1 ≤ K ≤ 10^{5}
1 ≤ Arr[i] ≤ 10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



def ReducingWalls (arr, n, k) : 

    #Complete the function

    

Solutions:
def ReducingWalls(arr, n, k):
	c = 0
	for i in arr:
		if i > k:
			c += (i - 1) // k
	return c


def ReducingWalls(arr, n, k):
	count = 0
	for elem in arr:
		q = elem // k
		count += 0 if elem <= k else q - 1 if elem % k == 0 else q
	return count


def ReducingWalls(arr, n, k):
	i = 0
	count = 0
	while i < n:
		if arr[i] > k:
			count += (arr[i] - 1) // k
		i += 1
	return count


import math

def ReducingWalls(arr, n, k):
	power = 0
	for i in arr:
		if i > k:
			power += (i - 1) // k
	return power


from math import ceil

def ReducingWalls(arr, n, k):
	l = []
	for i in range(n):
		if arr[i] > k:
			l.append(arr[i])
	c = 0
	for i in l:
		c += ceil((i - k) / k)
	return c


def ReducingWalls(arr, n, k):
	ans = 0
	for num in arr:
		ans += (num - 1) // k
	return ans


def ReducingWalls(arr, n, k):
	summa = 0
	for item in arr:
		summa += (item - 1) // k
	return summa


def ReducingWalls(arr, n, k):
	p = 0
	for j in arr:
		if j > k and j % k != 0:
			p += j // k
		elif j > k and j % k == 0:
			p += j // k - 1
	return p


def ReducingWalls(arr, n, k):
	count = 0
	for i in range(n):
		if arr[i] > k:
			count = count + (arr[i] - 1) // k
		if arr[i] <= k:
			continue
	return count


def ReducingWalls(arr, n, k):
	ans = 0
	for i in range(len(arr)):
		b = arr[i]
		c = 0
		if b > k:
			c = (b - 1) // k
			ans += c
	return ans


def ReducingWalls(arr, n, k):
	ans = 0
	for x in arr:
		ans += x // k
		if x % k == 0:
			ans -= 1
	return ans


def ReducingWalls(arr, n, k):
	cnt = 0
	for val in arr:
		if val > k:
			cnt += (val - 1) // k
	return cnt


def ReducingWalls(arr, n, k):
	count = 0
	for i in arr:
		if i > k:
			if i % k == 0:
				count = count + i // k - 1
			else:
				count = count + i // k
	return count


def ReducingWalls(arr, n, k):
	return sum([(each - 1) // k for each in arr if each > k])


import math

def ReducingWalls(arr, n, k):
	c = 0
	for i in arr:
		if i > k:
			c += math.ceil((i - k) / k)
	return c


def ReducingWalls(arr, n, k):
	min_times = 0
	for i in range(n):
		if arr[i] > k:
			min_times += (arr[i] - 1) // k
	return min_times


import math

def ReducingWalls(arr, n, k):
	count = 0
	for ele in arr:
		if ele > k:
			ele = ele - k
			count += math.ceil(ele / k)
	return count


def ReducingWalls(arr, n, k):
	ct = 0
	for x in arr:
		if x > k:
			ct = ct + (x - 1) // k
	return ct
for _ in range(0, int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().strip().split()))
	ans = ReducingWalls(arr, n, k)
	print(ans)


def ReducingWalls(arr, n, k):
	count = 0
	for i in arr:
		if i > k:
			count = count + (i - 1) // k
	return count
for _ in range(0, int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().strip().split()))
	ans = ReducingWalls(arr, n, k)
	print(ans)


def ReducingWalls(arr, n, k):
	power = 0
	for itr in range(n):
		if arr[itr] > k:
			p = arr[itr] / k
			power += int(p)
			if p.is_integer():
				power -= 1
	return power
for _ in range(0, int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().strip().split()))
	ans = ReducingWalls(arr, n, k)
	print(ans)


def ReducingWalls(arr, n, k):
	powerUse = 0
	for i in range(0, n):
		if arr[i] > k and arr[i] % k != 0:
			powerUse += int(arr[i] / k)
		elif arr[i] > k:
			powerUse += int(arr[i] / k) - 1
	return powerUse


def ReducingWalls(a, n, k):
	count = 0
	for i in range(n):
		if a[i] > k:
			if a[i] % k == 0:
				count += a[i] // k - 1
			else:
				count += a[i] // k
	return count


def ReducingWalls(arr, n, k):
	sol = []
	for i in arr:
		if i > k:
			sol.append((i - 1) // k)
	return sum(sol)