将数组的所有元素减少为零所需的最少步骤

本文概述

• C ++
• Java
• Python3
• C#

给定一个数组arr []对正整数, 任务是找到最小的步骤, 以减少所有元素为0。一步, -1可以同时添加到数组的所有非零元素中。

例子：

输入：arr [] = {1, 5, 6}
输出：6
操作1：arr [] = {0, 4, 5}
操作2：arr [] = {0, 3, 4}
操作3：arr [] = {0, 2, 3}
运算4：arr [] = {0, 1, 2}
运算5：arr [] = {0, 0, 1}
运算6：arr [] = {0, 0, 0}
输入：arr [] = {1, 1}
输出：1

简单的方法：一种简单的方法是先对数组进行排序, 然后从最小元素开始, 计算将其减少到0所需的步骤数。然后, 从下一个数组元素开始减少此计数, 因为所有元素将同时更新。

高效的方法：可以看到, 最小步数将始终等于数组中的最大元素。

下面是上述方法的实现：

C ++

//C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
  
//Function to return the minimum steps
//required to reduce all the elements to 0
int minSteps( int arr[], int n)
{
  
     //Maximum element from the array
     int maxVal = *max_element(arr, arr + n);
     return maxVal;
}
  
//Driver code
int main()
{
     int arr[] = { 1, 2, 4 };
     int n = sizeof (arr) /sizeof ( int );
  
     cout <<minSteps(arr, n);
  
     return 0;
}

Java

//Java implementation of the approach
class GFG 
{
      
     //method to get maximum number from array elements
     static int getMax( int inputArray [])
     {
         int maxValue = inputArray[ 0 ];
  
         for ( int i = 1 ; i <inputArray.length; i++)
         {
             if (inputArray[i]> maxValue)
             {
                 maxValue = inputArray[i];
             }
         }
         return maxValue;
     }
      
     //Function to return the minimum steps 
     //required to reduce all the elements to 0 
     static int minSteps( int arr[], int n) 
     { 
      
         //Maximum element from the array 
         int maxVal = getMax(arr); 
         return maxVal; 
     } 
      
     //Driver code 
     public static void main (String[] args) 
     { 
         int arr[] = { 1 , 2 , 4 }; 
         int n = arr.length; 
      
         System.out.println(minSteps(arr, n)); 
     } 
}
  
//This code is contributed by AnkitRai01

Python3

# Python3 implementation of the approach
  
# Function to return the minimum steps
# required to reduce all the elements to 0
def minSteps(arr, n):
  
     # Maximum element from the array
     maxVal = max (arr)
     return maxVal
  
# Driver code
arr = [ 1 , 2 , 4 ]
n = len (arr)
  
print (minSteps(arr, n))
  
# This code is contributed by Mohit Kumar

C#

//C# implementation of the approach
using System;
  
class GFG 
{
      
     //method to get maximum number from array elements
     static int getMax( int []inputArray)
     {
         int maxValue = inputArray[0];
  
         for ( int i = 1; i <inputArray.Length; i++)
         {
             if (inputArray[i]> maxValue)
             {
                 maxValue = inputArray[i];
             }
         }
         return maxValue;
     }
      
     //Function to return the minimum steps 
     //required to reduce all the elements to 0 
     static int minSteps( int []arr, int n) 
     { 
      
         //Maximum element from the array 
         int maxVal = getMax(arr); 
         return maxVal; 
     } 
      
     //Driver code 
     public static void Main(String []args) 
     { 
         int []arr = { 1, 2, 4 }; 
         int n = arr.Length; 
      
         Console.WriteLine(minSteps(arr, n)); 
     } 
}
  
//This code is contributed by Arnab Kundu

输出如下：

4

---