12

Count of iterations to make minimum as 0 by rotating Array followed by reducing...

 3 years ago
source link: https://www.geeksforgeeks.org/count-of-iterations-to-make-minimum-as-0-by-rotating-array-followed-by-reducing-it-from-original-array/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
Like Article

Count of iterations to make minimum as 0 by rotating Array followed by reducing it from original Array

  • Last Updated : 12 Jan, 2022

Given an array arr[]. The task is to find the number of iterations required to make the minimum element in the array as 0. In one iteration, left rotate the array by one and subtract the corresponding element of the original array and rotated array.

Examples:

Input: arr[] = { 2, 6, 3, 4, 8, 7 }
Output: 3
Explanation: Refer to the image below for explanation.

Screenshot91-660x521.png

Input: arr[] = { 4, 10, 12, 3, 9, 7 }
Output: 5

Naive Approach: The easiest way to solve this problem is by using the Greedy Approach.

  • Simply pop the first element of the array and append it to the end and then perform the subtraction on the corresponding element.
  • Similarly, perform the same operation on the resultant array till we get minimum element in an array as zero, and return the count of iteration.

Below is the implementation of the above approach

  • Python3
# Python program for above approach
# Function to find no of iterations.
def minZero(A, n):
# Initialize count c = 0.
c = 0
# if zero is already present 
# in array return c.
if min(A) == 0:
return c
# Iterate till minimum 
# in array becomes zero.
while min(A) != 0:
# Copy array element to A1
A1 = A[:]
# Pop first element and
# append it to last
x = A.pop(0)
A.append(x)
# Perform subtarction
for i in range(n):
A[i] = abs(A[i]-A1[i])
# Increament count by 1
c += 1
# Return value of count c
return c
# Driver Code
# Original array
arr = [2, 6, 3, 4, 8, 7]
# Calling method minZero
x = minZero(arr, len(arr))
# Print the result
print(x)
Output
3

Time Complexity:  O(N)
Auxiliary Space:  O(N)

Efficient Approach: A space-optimized approach is a logic and implementation-based. Follow the steps below to solve the given problem. 

  • Store the first element of array in variable x.
  • Now find absolute difference between consecutive elements.
  • Replace result from index 0.
  • Subtract last element from variable x and store it.
  • count the iteration and repeat the steps. 
  • Return count as the final answer.

Screenshot94-660x304.png

Below is the implementation of the above approach

  • Python3
# Python program for above approach
# Function to find no of iterations
def minZero(A, n):
# Initialize count c = 0
c = 0
# If 0 already in array return c
if min(A) == 0:
return c
# Iterate till we get zero in array
while min(A) != 0:
# Assign first element in x
x = A[0]
# Loop to subtract consecutive element
for i in range(n-1):
A[i] = abs(A[i]-A[i + 1])
A[n-1] = abs(A[n-1]-x)
# Increment count c
c += 1
# Return c
return c
# Driver Code
# Original array
arr = [2, 6, 3, 4, 8, 7]
# Length of array
N = len(arr)
# calling function
x = minZero(arr, N)
# print the result
print(x)
Output
3

Time Complexity: O(N)
Auxiliary Space: O(1)


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK