Длина наименьшего подмассива в диапазоне от 1 до N с суммой, превышающей заданное значение

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

Учитывая два числа N и S , задача состоит в том, чтобы найти длину наименьшего подмассива в диапазоне (1, N), такую, чтобы сумма этих выбранных чисел была больше, чем S.

Примеры:

Input: N = 5, S = 11 
Output: 3 
Explanation: 
Smallest subarray with sum > 11 = {5, 4, 3}

Input: N = 4, S = 7 
Output: 3 
Explanation: 
Smallest subarray with sum > 7 = {4, 3, 2} 
 

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

Наивный подход: метод грубой силы заключается в выборе элементов в обратном порядке до тех пор, пока сумма всех выбранных элементов не станет меньше или равна заданному числу.

Ниже представлена реализация описанного выше подхода.

C ++

// C++ implementation of the above implementation
#include <bits/stdc++.h>
using namespace std;
// Function to return the count
// of minimum elements such that
// the sum of those elements is > S.
int countNumber( int N, int S)
{
int countElements = 0;
// Initialize currentSum = 0
int currSum = 0;
// Loop from N to 1 to add the numbers
// and check the condition.
while (currSum <= S) {
currSum += N;
N--;
countElements++;
}
return countElements;
}
// Driver code
int main()
{
int N, S;
N = 5;
S = 11;
int count = countNumber(N, S);
cout << count << endl;
return 0;
}

Джава

// Java implementation of the above implementation
class GFG
{
// Function to return the count
// of minimum elements such that
// the sum of those elements is > S.
static int countNumber( int N, int S)
{
int countElements = 0 ;
// Initialize currentSum = 0
int currSum = 0 ;
// Loop from N to 1 to add the numbers
// and check the condition.
while (currSum <= S)
{
currSum += N;
N--;
countElements++;
}
return countElements;
}
// Driver code
public static void main (String[] args)
{
int N, S;
N = 5 ;
S = 11 ;
int count = countNumber(N, S);
System.out.println(count);
}
}
// This code is contributed by AnkitRai01

Python

# Python implementation of the above implementation
# Function to return the count
# of minimum elements such that
# the sum of those elements is > S.
def countNumber(N, S):
countElements = 0 ;
currentSum = 0
currSum = 0 ;
# Loop from N to 1 to add the numbers
# and check the condition.
while (currSum < = S) :
currSum + = N;
N = N - 1 ;
countElements = countElements + 1 ;
return countElements;
# Driver code
N = 5 ;
S = 11 ;
count = countNumber(N, S);
print (count) ;
# This code is contributed by Shivi_Aggarwal

C #

// C# implementation of the above implementation
using System;
class GFG
{
// Function to return the count
// of minimum elements such that
// the sum of those elements is > S.
static int countNumber( int N, int S)
{
int countElements = 0;
// Initialize currentSum = 0
int currSum = 0;
// Loop from N to 1 to add the numbers
// and check the condition.
while (currSum <= S)
{
currSum += N;
N--;
countElements++;
}
return countElements;
}
// Driver code
public static void Main()
{
int N, S;
N = 5;
S = 11;
int count = countNumber(N, S);
Console.WriteLine(count);
}
}
// This code is contributed by AnkitRai01

Javascript

<script>
// JavaScript implementation of the above implementation
// Function to return the count
// of minimum elements such that
// the sum of those elements is > S.
function countNumber(N, S)
{
let countElements = 0;
// Initialize currentSum = 0
let currSum = 0;
// Loop from N to 1 to add the numbers
// and check the condition.
while (currSum <= S)
{
currSum += N;
N--;
countElements++;
}
return countElements;
}
// Driver code
let N, S;
N = 5;
S = 11;
let count = countNumber(N, S);
document.write(count + "<br>" );
// This code is contributed by Surbhi Tyagi.
</script>
Выход:
 3

Сложность времени: O (N)

Эффективный подход: идея состоит в том, чтобы использовать концепцию двоичного поиска для решения проблемы.
Из концепции двоичного поиска известно, что эту концепцию можно применить, когда известно, что в проблеме есть порядок. То есть для каждой итерации, если можно точно определить, что требуемый ответ находится либо в первой, либо во второй половине (т. Е.), В задаче существует шаблон.
Следовательно, бинарный поиск можно применить к диапазону следующим образом:

  1. Инициализировать start = 1 и end = N.
  2. Найдите mid = start + (end - start) / 2.
  3. Если сумма всех элементов от последнего элемента до среднего элемента меньше или равна заданной сумме, то end = mid, else start = mid + 1.
  4. Повторите шаг 2, пока начало меньше конца.

Ниже представлена реализация описанного выше подхода.

C ++

// C++ implementation of the above approach.
#include <iostream>
using namespace std;
// Function to do a binary search
// on a given range.
int usingBinarySearch( int start, int end,
int N, int S)
{
if (start >= end)
return start;
int mid = start + (end - start) / 2;
// Total sum is the sum of N numbers.
int totalSum = (N * (N + 1)) / 2;
// Sum until mid
int midSum = (mid * (mid + 1)) / 2;
// If remaining sum is < the required value,
// then the required number is in the right half
if ((totalSum - midSum) <= S) {
return usingBinarySearch(start, mid, N, S);
}
return usingBinarySearch(mid + 1, end, N, S);
}
// Driver code
int main()
{
int N, S;
N = 5;
S = 11;
cout << (N - usingBinarySearch(1, N, N, S) + 1)
<< endl;
return 0;
}

Джава

// Java implementation of the above approach.
class GFG
{
// Function to do a binary search
// on a given range.
static int usingBinarySearch( int start, int end,
int N, int S)
{
if (start >= end)
return start;
int mid = start + (end - start) / 2 ;
// Total sum is the sum of N numbers.
int totalSum = (N * (N + 1 )) / 2 ;
// Sum until mid
int midSum = (mid * (mid + 1 )) / 2 ;
// If remaining sum is < the required value,
// then the required number is in the right half
if ((totalSum - midSum) <= S)
{
return usingBinarySearch(start, mid, N, S);
}
return usingBinarySearch(mid + 1 , end, N, S);
}
// Driver code
public static void main (String[] args)
{
int N, S;
N = 5 ;
S = 11 ;
System.out.println(N - usingBinarySearch( 1 , N, N, S) + 1 ) ;
}
}
// This code is contributed by AnkitRai01

Python3

# Python3 implementation of the above approach.
# Function to do a binary search
# on a given range.
def usingBinarySearch(start, end, N, S) :
if (start > = end) :
return start;
mid = start + (end - start) / / 2 ;
# Total sum is the sum of N numbers.
totalSum = (N * (N + 1 )) / / 2 ;
# Sum until mid
midSum = (mid * (mid + 1 )) / / 2 ;
# If remaining sum is < the required value,
# then the required number is in the right half
if ((totalSum - midSum) < = S) :
return usingBinarySearch(start, mid, N, S);
return usingBinarySearch(mid + 1 , end, N, S);
# Driver code
if __name__ = = "__main__" :
N = 5 ;
S = 11 ;
print (N - usingBinarySearch( 1 , N, N, S) + 1 ) ;
# This code is contributed by AnkitRai01

C #

// C# implementation of the above approach.
using System;
class GFG
{
// Function to do a binary search
// on a given range.
static int usingBinarySearch( int start, int end,
int N, int S)
{
if (start >= end)
return start;
int mid = start + (end - start) / 2;
// Total sum is the sum of N numbers.
int totalSum = (N * (N + 1)) / 2;
// Sum until mid
int midSum = (mid * (mid + 1)) / 2;
// If remaining sum is < the required value,
// then the required number is in the right half
if ((totalSum - midSum) <= S)
{
return usingBinarySearch(start, mid, N, S);
}
return usingBinarySearch(mid + 1, end, N, S);
}
// Driver code
public static void Main()
{
int N, S;
N = 5;
S = 11;
Console.WriteLine(N - usingBinarySearch(1, N, N, S) + 1) ;
}
}
// This code is contributed by AnkitRai01

Javascript

<script>
// Javascript implementation of the above approach.
// Function to do a binary search
// on a given range.
function usingBinarySearch(start, end, N, S)
{
if (start >= end)
return start;
let mid = start + (end - start) / 2;
// Total sum is the sum of N numbers.
let totalSum = (N * (N + 1)) / 2;
// Sum until mid
let midSum = (mid * (mid + 1)) / 2;
// If remaining sum is < the required value,
// then the required number is in the right half
if ((totalSum - midSum) <= S)
{
return usingBinarySearch(start, mid, N, S);
}
return usingBinarySearch(mid + 1, end, N, S);
}
// Driver code
let N, S;
N = 5;
S = 11;
document.write((N - usingBinarySearch(
1, N, N, S) + 1) + "<br>" );
// This code is contributed by Mayank Tyagi
</script>
Выход:
 3

Сложность времени: O (log N)

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

Technical Scripter

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

Количество чисел между L и R, взаимно простых с P
27 Февраля, 2023
Постройте матрицу, каждая строка и столбец которой содержат N и M единиц соответственно.
27 Февраля, 2023
Максимизируйте сумму трех чисел, выполнив побитовое XOR
27 Февраля, 2023
Проверьте, совпадает ли набор первых элементов X одного массива с набором первых элементов Y другого
27 Февраля, 2023
Подсчитать подстроки нечетной длины с медианой, такой же, как K-й символ строки
27 Февраля, 2023
Найти лексикографически первый идентификатор каждого домена из заданного массива идентификаторов электронной почты
27 Февраля, 2023
Найдите общее количество фигур 'X'
26 Февраля, 2023
Максимальное значение узла, которое может быть достигнуто с использованием данных соединений
26 Февраля, 2023