The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Arrays & Strings

Problem :-
Given an array of 'n' elements & and a window of size 'p', find if there exists a subarray of consecutive elements of size 'p' which sums to a given value 'x'.
Consider array { 2, 4, -3, 7, -1} , Window size = 3 & Target value = 8
We see that subarray = { 4, -3, 7 } of size 3 has sum = 8

Solution :-
We will follow a sliding window approach i.e consider the window of size p starting at index 0.
If the sum of all elements within the window is not equal to 'x', then shift the window by one position towards right. See the efficient implementation below.

#include<iostream>
using namespace std;

// find a window of size 'p' with sum of elements = target
bool isSubarrayPresent(int arr[],int size,int p,int target) {
   int i;
   // start and end index of window of size 'p'
   int start_window_idx = 0;
   int end_window_idx = 0;
   int sum = 0;
   for (i=0;i<size;i++) {
      sum += arr[i];
      end_window_idx++;
      if (sum == target && (end_window_idx - start_window_idx) == p) {
         // window of 'p' elements with sum = target found
         return true;
      }
      if ((end_window_idx - start_window_idx) == p) {
         // sum of elements in current window is not equal to target
         // shift the window by one position
         sum -= arr[start_window_idx];
         start_window_idx++;
      }
   }
   return false;
}

// main
int main() {
   int arr[] = { 1,4,-2,6,-3,7,1,3,-6,1 };
   int size = sizeof(arr)/sizeof(arr[0]);
   int p = 4;
   int target = -1;
   bool found = isSubarrayPresent(arr,size,p,target);
   if (found) {
      cout<<"\nSubarray of "<<p<<" elements with sum "<<target<<" found";
   } else {
      cout<<"\nSubarray of "<<p<<" elements with sum "<<target<<" not found";
   }
   cout<<endl;
   return 0;
}

Back | Next

All problems on Arrays and Strings
* Reverse an array in place
* Sort an array of 0s and 1s
* Sort an array of 0s, 1s and 2s
* Print all the maxima elements in the array
* Check if two strings are anagrams
* Find the duplicate array elements
* Find the minimum element in a sorted and rotated array
* Remove all duplicate characters in a string
* Find two array elements which sum upto a target value
* Find the median of two sorted arrays
* Find if a sub-array of consecutive elements of size p exists which sum upto a target value
* Find the maximum difference between two elements in an array s.t larger element appears after the smaller element in the array
* Find the largest sum contiguous subarray
* Find the smallest positive element missing in the given array of size n consisting of both positive & negative integers
* Given an array of n elements, find max( j - i ) s.t arr(j) > arr(i)