Длина наименьшего подмассива в диапазоне от 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 и многому другому, см. Полный курс подготовки к собеседованию .

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

Проверить делимость на 7
21 Января, 2022
Подсчитайте числа, не содержащие 3
21 Января, 2022
Печатать граничные элементы заданной матрицы по часовой стрелке
21 Января, 2022
Программа для нахождения суммы ряда 1 + 1/2 + 1/3 + 1/4 + .. + 1 / n
21 Января, 2022
Программа C для печати треугольника Флойда
21 Января, 2022
Программа для печати первых n чисел Фибоначчи | Комплект 1
21 Января, 2022
Программа для поиска площади круга
21 Января, 2022
Программа для поиска площади треугольника
21 Января, 2022