Consider an integer sequence A = {1, 2, 3, …., N} i.e. the first N natural numbers in order and two integers, L and S. Check whether there exists a subarray of length L and sum S after removing at most one element from A.
Examples:
Input: N = 5, L = 3, S = 11
Output: YES
Explanation: We can remove 3 from A to obtain A = {1, 2, 4, 5} where {2, 4, 5} is a required subarray of size 3 and sum 11.Input: N = 5, L = 3, S = 5
Output: NO
Explanation: For the above input its not possible to determine a subarray with the required conditions.
Approach: The problem can be solved based on the following observation:
The observations are
- The first observation is that if the given sum is less than the minimum sum or greater than the maximum sum then it is obvious that we can’t form or find a subarray. The minimum sum would be the sum of the first L natural numbers and the maximum sum would be the sum of the last L natural numbers.
- The second observation is that if the given sum is in between the minimum and maximum sum then it is always possible to obtain the sum because the sequence contains all the numbers in the natural numbers order so that we can always make a sub-array with the given sum provided by removing at most one element from the sequence.
Follow the steps mentioned below to implement the idea:
- First find out the sum of the first L natural numbers and the sum of the last L natural numbers.
- The sum of the first N natural numbers (N * (N + 1))/2.
- So the sum of the last L natural numbers can be found like this: sum of first N natural numbers – sum of first (N-L) natural numbers.
- Check if S lies within the range of [sum of first L natural number, sum of last L natural numbers]. If the condition is satisfied then the sum exists.
Below is the implementation of the above approach.
C++
// C++ code to implement the idea#include <bits/stdc++.h>using namespace std;// Function the return sum of first N natural numbersint findSum(int n){ return n * (n + 1) / 2;}// Function to check if the sum existsbool isPossible(int n, int l, int s){ // Minimum sum will be sum of first l numbers int minimumSum = findSum(l); // Maximum sum will be sum of last l numbers int maximumSum = findSum(n) - findSum(n - l); // Checking if the given sum is not falling within the // range then print NO else Print YES if (s < minimumSum || s > maximumSum) return false; return true;}// Driver codeint main(){ int N = 5, L = 3, S = 11; // Function call if (isPossible(N, L, S)) cout << "YES"; else cout << "NO"; return 0;} |
Java
public class GFG { // Function to return the sum of first N natural numbers static int findSum(int n) { return n * (n + 1) / 2; } // Function to check if the sum exists static boolean isPossible(int n, int l, int s) { // Minimum sum will be sum of first l numbers int minimumSum = findSum(l); // Maximum sum will be sum of last l numbers int maximumSum = findSum(n) - findSum(n - l); // Checking if the given sum is not falling within the // range then return false else return true if (s < minimumSum || s > maximumSum) return false; return true; } public static void main(String[] args) { int N = 5, L = 3, S = 11; // Function call if (isPossible(N, L, S)) System.out.println("YES"); else System.out.println("NO"); }}// this code is contributed by uttamdp_10 |
Python3
# python code to implement the idea# Function to return the sum of first N natural numbersdef findSum(n): return n * (n + 1) // 2# Function to check if the sum existsdef isPossible(n, l, s): # Minimum sum will be the sum of the first l numbers minimumSum = findSum(l) # Maximum sum will be the sum of the last l numbers maximumSum = findSum(n) - findSum(n - l) # Checking if the given sum is not falling within the range if s < minimumSum or s > maximumSum: return False return True# Driver codeN = 5L = 3S = 11# Function callif isPossible(N, L, S): print("YES")else: print("NO") |
C#
// c# code to implement the ideausing System;class GFG{ // Function that returns the sum of the first N natural numbers static int FindSum(int n) { return n * (n + 1) / 2; } // Function to check if the sum exists static bool IsPossible(int n, int l, int s) { // Minimum sum will be the sum of the first l numbers int minimumSum = FindSum(l); // Maximum sum will be the sum of the last l numbers int maximumSum = FindSum(n) - FindSum(n - l); // Checking if the given sum falls within the range, // then return true; otherwise, return false if (s < minimumSum || s > maximumSum) return false; return true; } static void Main(string[] args) { int N = 5, L = 3, S = 11; // Function call if (IsPossible(N, L, S)) Console.WriteLine("YES"); else Console.WriteLine("NO"); }} |
Javascript
// Function the return sum of first N natural numbersfunction findSum(n) { return n * (n + 1) / 2;}// Function to check if the sum existsfunction isPossible(n, l, s) { // Minimum sum will be sum of first l numbers let minimumSum = findSum(l); // Maximum sum will be sum of last l numbers let maximumSum = findSum(n) - findSum(n - l); // Checking if the given sum is not falling within the // range then return false else return true if (s < minimumSum || s > maximumSum) return false; return true;}// Driver codelet N = 5, L = 3, S = 11;// Function callif (isPossible(N, L, S)) console.log("YES");else console.log("NO"); |
Output
YES
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
