Sub-array with given sum in C

Sub-array with given sum

Here, in this page we will write the program for sub-array with given sum in C.Given an Array of non negative Integers and a number. You need to print all the starting and ending indices of Sub-arrays having their sum equal to the given integer.
Example : arr[ ] = {1, 4, 0, 0, 3, 10, 5}, sum = 7
Output : Sum found between indexes 1 and 4 Sum of elements between indices 1 and 4 is (4 + 0 + 0 + 3) = 7

sub-array with given sum

Sub-Array With Given Sum in C

A Sub-array with given sum code in C is a program that takes an array of integers and a target sum as input, and finds a contiguous subarray within the array that adds up to the target sum. The program then outputs the starting and ending indices of the subarray, or indicates if no such subarray exists.

On this page we will discuss two different methods for this-

  1. Naive Approach
  2. Sliding Window Approach
Sub-array with given sum
  1. Naive approach: Naive approach uses a nested loop to check all possible subarrays of the given array. For each starting index i, it checks all subarrays starting from i and ending at j, and calculates their sum. If the sum is equal to the given sum, it prints the indices of the subarray and returns. If no subarray is found, it prints a message indicating that no subarray was found.

Algorithm:

Step 1: Take the input array and target sum as input.
Step 2: Traverse the array from the first element to the last element.
Step 3: For each element i, initialize the current sum as arr[i].
Step 4: Traverse the array from i+1 to n, where n is the length of the array.
Step 5: For each element j, add arr[j] to the current sum.
Step 6: If the current sum is equal to the target sum, print the starting and ending indices of the subarray and return.
Step 7: If the current sum is greater than the target sum or j is equal to n, break out of the loop and continue with the next element i.
Step 8: If no subarray is found, print a message indicating that no subarray was found.

C Code for naive approach

Run
#include <stdio.h>

void findSubarray(int arr[], int n, int sum)
{
    for (int i = 0; i < n; i++) {
        int curr_sum = 0;

        for (int j = i; j < n; j++) {
            curr_sum += arr[j];

            if (curr_sum == sum) {
                printf("Subarray found between indexes %d and %d\n", i, j);
                return;
            }
        }
    }

    printf("No subarray found\n");
}

int main()
{
    int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = 23;

    findSubarray(arr, n, sum);

    return 0;
}

Output

Subarray found between indexes 1 and 4
  1. Sliding Window approach:It uses a sliding window approach, where a window of elements is moved from left to right to find the sum. The start and end of the window are stored as variables and updated as necessary. If a subarray with the sum is found, its indices are printed to the console. Otherwise, a message indicating that no subarray was found is printed.

Algorithm:

Step 1: Take the input array and target sum as input.
Step 2: Initialize two variables, start and curr_sum, to the first element of the array.
Step 3: Traverse the array from the second element to the last element.
Step 4: If the current sum is greater than the target sum, increment start and subtract arr[start-1] from curr_sum until curr_sum is less than or equal to the target sum.
Step 5: If the current sum is equal to the target sum, print the starting and ending indices of the subarray and return.
Step 6: If the current sum is less than the target sum and i is less than n, add arr[i] to curr_sum and continue with the next element i.
Step 7: If no subarray is found, print a message indicating that no subarray was found.

C Code for sliding window approach

Run
#include <stdio.h>

void findSubarray(int arr[], int n, int sum)
{
    int curr_sum = arr[0];
    int start = 0;

    for (int i = 1; i <= n; i++) { while (curr_sum > sum && start < i - 1) {
            curr_sum = curr_sum - arr[start];
            start++;
        }

        if (curr_sum == sum) {
            printf("Subarray found between indexes %d and %d\n", start, i - 1);
            return;
        }

        if (i < n)
            curr_sum = curr_sum + arr[i];
    }

    printf("No subarray found\n");
}

int main()
{
    int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = 23;

    findSubarray(arr, n, sum);

    return 0;
}

Output

Subarray found between indexes 1 and 4

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Arrays

  • Introduction to Arrays – CC++ | Java
  • Introduction to 2-D Arrays – CC++ Java
  • Sorting of Array – C | C++ | Java
  • Array Rotation – CC++ | Java
  • Reverse an array or string- CC++ | Java
  • Find pairs in array with given sum – CC++ | Java
  • Sort the array in Waveform – CC++ | Java
  • Majority Element in Array – CC++ | Java
  • Boyer-Moore’s Voting Algorithm – CC++ | Java
  • K-pairs with smallest sum in 2 arrays – C | C++ | Java
  • Largest Sum Contigous SubArray – CC++ | Java
  • Maximum Average Sub-array of K length – CC++ | Java
  • Size of sub-array with max sum – CC++ | Java
  • Sub-array with given sum – CC++ | Java
  • Triplet that sum to a given value – CC++ | Java
  • Segregate 0’s and 1’s in array – CC++ | Java
  • Segregate 0’s 1’s and 2’s in array – CC++ | Java
  • Sort elements in array by frequency – CC++ | Java
  • Finding pythagorean triplets in an array – CC++ | Java
  • Reorder array using given indexes – CC++ | Java
  • Merging two sorted arrays – CC++ | Java
  • Minimum number of Merge Operations to make an Array Palindrome – CC++ | Java
  • Find Zeros to be Flipped so that number of Consecutive 1’s is maximized – CC++ | Java

Sub-array with Given Sum in Java

Sub-array with Given Sum

Here, in this page we will write the program for sub-array with given sum in Java. Given an Array of non negative Integers and a number. You need to print all the starting and ending indices of Sub-arrays having their sum equal to the given integer . We will understand this problem in detail with algorithm and code in Java.

Sub array with given sum in Java

Sub-Array With Given Sum in Java

A Sub-array with given sum code in Java is a program that  to a contiguous subsequence of elements within an array that has a sum equal to a specific target value. In other words, it is a consecutive sequence of elements in an array whose sum is equal to a given sum value. The goal is to find such a sub-array within the given array.

Example : arr[ ] = {1, 4, 0, 0, 3, 10, 5}, sum = 7
Output : Sum found between indexes 1 and 4 Sum of elements between indices 1 and 4 is (4 + 0 + 0 + 3) = 7

On this page we will discuss two different methods for this-

  1. Naive Approach
  2. Sliding Window Approach
Sub-array with given sum in Java
  1. Naive approach: The naive approach to find a sub-array with a given sum in Java involves using a nested loop to check all possible sub-arrays of the given array. For each starting index ‘i’, it checks all sub-arrays starting from ‘i’ and ending at ‘j’, and calculates their sum. If the sum matches the given sum, it prints the indices of the sub-array and returns. If no -with the sum is found, it prints a message indicating the absence of such a sub-array.

Algorithm:

  1. Take the input array arr and target sum sum as input.
  2. Initialize curr_sum to 0.
  3. Traverse the array arr from the first element to the last element with a loop variable i ranging from 0 to n-1, where n is the length of the array.
  4. For each i:
    1. Initialize curr_sum as arr[i].
    2. Traverse the array arr from i+1 to n with a loop variable j ranging from i+1 to n-1.
    3. For each j:
      1. Add arr[j] to curr_sum.
      2. If curr_sum is equal to the target sum, print the starting and ending indices of the sub-array as “Subarray found between indexes i and j” and return.
      3. If curr_sum is greater than the target sum or j is equal to n-1, break out of the loop and continue with the next element i.
  5. If no sub-array is found, print “No sub-array found”.

Java code for Naive Approach

Run
import java.util.*;

public class Main {
    
    public static void findSubarray(ArrayList< Integer> arr, int sum) {
        int n = arr.size();
        
        for (int i = 0; i < n; i++) {
            int currSum = 0;
            
            for (int j = i; j < n; j++) {
                currSum += arr.get(j);
                
                if (currSum == sum) {
                    System.out.println("Subarray found between indexes " + i + " and " + j);
                    return;
                }
            }
        }
        
        System.out.println("No subarray found");
    }
    
    public static void main(String[] args) {
        ArrayList arr = new ArrayList<>(Arrays.asList(15, 2, 4, 8, 9, 5, 10, 23));
        int sum = 23;
        
        findSubarray(arr, sum);
    }
}

Output

Subarray found between indexes 1 and 4
  1. Sliding Window approach:The code uses a sliding window approach to search for a sub-array with a given sum. The window, represented by the variables ‘start’ and ‘i’, is moved from the left to the right of the array while maintaining a running sum ‘curr_sum’. If the current sum matches the target sum, the indices of the sub-array are printed. If no sub-array with the sum is found, a message indicating the absence of such a sub-array is printed.

Algorithm:

  1. Take the input array arr and target sum sum as input.
  2. Initialize two variables, start and curr_sum, to the first element of the array, i.e., arr[0].
  3. Traverse the array arr from the second element to the last element with a loop variable i ranging from 1 to n-1, where n is the length of the array.
  4. For each i:
    1. Check if curr_sum is greater than the target sum.
    2. If so, increment start by 1 and subtract arr[start-1] from curr_sum until curr_sum is less than or equal to the target sum.
    3. If curr_sum is equal to the target sum, print the starting and ending indices of the subarray as “Subarray found between indexes start and i” and return.
    4. If curr_sum is less than the target sum and i is less than n, add arr[i] to curr_sum and continue with the next element i.
  5. If no subarray is found, print “No subarray found”.

Java Code for sliding window approach

Run
import java.util.*;

public class Main {
    public static void findSubarray(int[] arr, int n, int sum) {
        int curr_sum = arr[0];
        int start = 0;

        for (int i = 1; i <= n; i++) {
            while (curr_sum > sum && start < i - 1) {
                curr_sum = curr_sum - arr[start];
                start++;
            }

            if (curr_sum == sum) {
                System.out.println("Subarray found between indexes " + start + " and " + (i - 1));
                return;
            }

            if (i < n)
                curr_sum = curr_sum + arr[i];
        }

        System.out.println("No subarray found");
    }

    public static void main(String[] args) {
        int[] arr = { 15, 2, 4, 8, 9, 5, 10, 23 };
        int n = arr.length;
        int sum = 23;

        findSubarray(arr, n, sum);
    }
}

Output

Subarray found between indexes 1 and 4

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Arrays

  • Introduction to Arrays – CC++ | Java
  • Introduction to 2-D Arrays – CC++ Java
  • Sorting of Array – C | C++ | Java
  • Array Rotation – CC++ | Java
  • Reverse an array or string- CC++ | Java
  • Find pairs in array with given sum – CC++ | Java
  • Sort the array in Waveform – CC++ | Java
  • Majority Element in Array – CC++ | Java
  • Boyer-Moore’s Voting Algorithm – CC++ | Java
  • K-pairs with smallest sum in 2 arrays – C | C++ | Java
  • Largest Sum Contigous SubArray – CC++ | Java
  • Maximum Average Sub-array of K length – CC++ | Java
  • Size of sub-array with max sum – CC++ | Java
  • Sub-array with given sum – CC++ | Java
  • Triplet that sum to a given value – CC++ | Java
  • Segregate 0’s and 1’s in array – CC++ | Java
  • Segregate 0’s 1’s and 2’s in array – CC++ | Java
  • Sort elements in array by frequency – CC++ | Java
  • Finding pythagorean triplets in an array – CC++ | Java
  • Reorder array using given indexes – CC++ | Java
  • Merging two sorted arrays – CC++ | Java
  • Minimum number of Merge Operations to make an Array Palindrome – CC++ | Java
  • Find Zeros to be Flipped so that number of Consecutive 1’s is maximized – CC++ | Java
WordPress › Error

There has been a critical error on this website.

Learn more about troubleshooting WordPress.