Минимальное количество удаляемых элементов, чтобы сумма оставшихся элементов была равна k

Опубликовано: 13 Января, 2022

Учитывая массив целых чисел arr [] и целое число k , задача состоит в том, чтобы найти минимальное количество целых чисел, которые необходимо удалить из массива, чтобы сумма оставшихся элементов была равна k . Если мы не можем получить требуемую сумму, выведите -1 .

Примеры:

Input: arr[] = {1, 2, 3}, k = 3
Output: 1
Either remove 1 and 2 to reduce the array to {3}
or remove 3 to get the array {1, 2}. Both have equal sum i.e. 3
But removing 3 requires only a single removal.
Input: arr[] = {1, 3, 2, 5, 6}, k = 5
Output: 3

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: идея состоит в том, чтобы использовать скользящее окно, и переменные j инициализируют его значением 0, min_num для хранения ответа и суммы для сохранения текущей суммы. Продолжайте добавлять элементы массива к переменной sum , пока она не станет больше или равной k, если она равна k, затем обновите min_num как минимум min_num и (n - (i + 1) + j) где n - количество целых чисел в массиве, а i - текущий индекс, иначе, если он больше k, тогда начните уменьшать сумму, удаляя значения массива из суммы до тех пор, пока сумма не станет меньше или равна k, а также увеличить значение j , если сумма равна k, то еще раз обновить min_num . Повторите весь этот процесс до конца массива.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to return the minimum number of
// integers that need to be removed from the
// array to form a sub-array with sum k
int FindMinNumber(int arr[], int n, int k)
{
    int i = 0;
    int j = 0;
  
    // Stores the minimum number of
    // integers that need to be removed
    // from the array
    int min_num = INT_MAX;
  
    bool found = false;
  
    int sum = 0;
  
    while (i < n) {
  
        sum = sum + arr[i];
  
        // If current sum is equal to
        // k, update min_num
        if (sum == k) {
            min_num = min(min_num, ((n - (i + 1)) + j));
            found = true;
        }
  
        // If current sum is greater than k
        else if (sum > k) {
  
            // Decrement the sum until it
            // becomes less than or equal to k
            while (sum > k) {
                sum = sum - arr[j];
                j++;
            }
            if (sum == k) {
                min_num = min(min_num, ((n - (i + 1)) + j));
                found = true;
            }
        }
  
        i++;
    }
  
    if (found)
        return min_num;
  
    return -1;
}
  
// Driver code
int main()
{
    int arr[] = { 1, 3, 2, 5, 6 };
    int n = sizeof(arr) / sizeof(int);
    int k = 5;
  
    cout << FindMinNumber(arr, n, k);
  
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
      
// Function to return the minimum number of
// integers that need to be removed from the
// array to form a sub-array with sum k
static int FindMinNumber(int arr[], int n, int k)
{
    int i = 0;
    int j = 0;
  
    // Stores the minimum number of
    // integers that need to be removed
    // from the array
    int min_num = Integer.MAX_VALUE;
  
    boolean found = false;
  
    int sum = 0;
  
    while (i < n) 
    {
  
        sum = sum + arr[i];
  
        // If current sum is equal to
        // k, update min_num
        if (sum == k)
        {
            min_num = Math.min(min_num, 
                             ((n - (i + 1)) + j));
            found = true;
        }
  
        // If current sum is greater than k
        else if (sum > k) 
        {
  
            // Decrement the sum until it
            // becomes less than or equal to k
            while (sum > k) 
            {
                sum = sum - arr[j];
                j++;
            }
            if (sum == k) 
            {
                min_num = Math.min(min_num, 
                                 ((n - (i + 1)) + j));
                found = true;
            }
        }
  
        i++;
    }
  
    if (found)
        return min_num;
  
    return -1;
}
  
// Driver code
public static void main(String[] args)
{
    int arr[] = { 1, 3, 2, 5, 6 };
    int n = arr.length;
    int k = 5;
  
    System.out.println(FindMinNumber(arr, n, k));
}
}
  
// This code is contributed by Code_Mech

Python3

# Python3 implementation of the approach
  
# Function to return the minimum number of
# integers that need to be removed from the
# array to form a sub-array with Sum k
def FindMinNumber(arr, n, k):
    i = 0
    j = 0
  
    # Stores the minimum number of
    # integers that need to be removed
    # from the array
    min_num = 10**9
  
    found = False
  
    Sum = 0
  
    while (i < n):
  
        Sum = Sum + arr[i]
  
        # If current Sum is equal to
        # k, update min_num
        if (Sum == k):
            min_num = min(min_num,
                        ((n - (i + 1)) + j))
            found = True
          
        # If current Sum is greater than k
        elif (Sum > k):
  
            # Decrement the Sum until it
            # becomes less than or equal to k
            while (Sum > k):
                Sum = Sum - arr[j]
                j += 1
            if (Sum == k):
                min_num = min(min_num, 
                            ((n - (i + 1)) + j))
                found = True
              
        i += 1
  
    if (found):
        return min_num
  
    return -1
  
# Driver code
arr = [1, 3, 2, 5, 6]
n = len(arr)
k = 5
  
print(FindMinNumber(arr, n, k))
  
# This code is contributed by mohit kumar

C#

// C# implementation of the approach
using System;
  
class GFG
{
      
// Function to return the minimum number of
// integers that need to be removed from the
// array to form a sub-array with sum k
static int FindMinNumber(int[] arr, int n, int k)
{
    int i = 0;
    int j = 0;
  
    // Stores the minimum number of
    // integers that need to be removed
    // from the array
    int min_num = int.MaxValue;
  
    bool found = false;
  
    int sum = 0;
  
    while (i < n) 
    {
  
        sum = sum + arr[i];
  
        // If current sum is equal to
        // k, update min_num
        if (sum == k)
        {
            min_num = Math.Min(min_num, 
                            ((n - (i + 1)) + j));
            found = true;
        }
  
        // If current sum is greater than k
        else if (sum > k) 
        {
  
            // Decrement the sum until it
            // becomes less than or equal to k
            while (sum > k) 
            {
                sum = sum - arr[j];
                j++;
            }
            if (sum == k) 
            {
                min_num = Math.Min(min_num, 
                                ((n - (i + 1)) + j));
                found = true;
            }
        }
  
        i++;
    }
  
    if (found)
        return min_num;
  
    return -1;
}
  
// Driver code
public static void Main()
{
    int[] arr = { 1, 3, 2, 5, 6 };
    int n = arr.Length;
    int k = 5;
  
    Console.WriteLine(FindMinNumber(arr, n, k));
}
}
  
// This code is contributed by Code_Mech

PHP

<?php
// PHP implementation of the approach
// Function to return the minimum number of
// integers that need to be removed from the
// array to form a sub-array with sum k
function FindMinNumber($arr,$n,$k)
{
    $i = 0;
    $j = 0;
  
    // Stores the minimum number of
    // integers that need to be removed
    // from the array
    $min_num = PHP_INT_MAX;
  
    $found = false;
  
    $sum = 0;
  
    while ($i < $n) 
    {
  
        $sum = $sum + $arr[$i];
  
        // If current sum is equal to
        // k, update min_num
        if ($sum == $k)
        {
            $min_num = min($min_num, 
                            (($n - ($i + 1)) + $j));
            $found = true;
        }
  
        // If current sum is greater than k
        else if ($sum > $k) 
        {
  
            // Decrement the sum until it
            // becomes less than or equal to k
            while ($sum > $k) 
            {
                $sum = $sum - $arr[$j];
                $j++;
            }
            if ($sum == $k) 
            {
                $min_num =min($min_num, 
                                (($n - ($i + 1)) + $j));
                $found = true;
            }
        }
  
        $i++;
    }
  
    if ($found)
        return $min_num;
  
    return -1;
}
  
// Driver code
$arr = array( 1, 3, 2, 5, 6 );
$n = sizeof($arr);
$k = 5;
  
echo(FindMinNumber($arr, $n, $k));
  
// This code is contributed by Code_Mech

Output:

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Алгоритмы Структуры данных

Минимальное количество удаляемых элементов, чтобы сумма оставшихся элементов была равна k

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

C++

Java

Python3

C#

PHP

РЕКОМЕНДУЕМЫЕ СТАТЬИ