How can we find a sub array in a 1-D array? Is there any other method other than brute force method?

It is not for maximum sum so we can't use kadane's algorithm.

Recommended Answers

All 8 Replies

what kind of an array are you talking about? use strchr() or strstr() with character arrays.

an array with numbers.

Most of the fast string searching algorithms can be applied to non-string arrays as well.

But I'm not not searching. I want to perform some operation on the subsets.(which is not sum) So how will string search algorithms help me?
I looked up one algortihm Boyer-Moore algorithm but it's not of any help.

That is really dependent of the nature of function applied and if there is overlap with previous answers and recursive function, you can sometimes reverse it to build dynamic programming solution or if it is difficult use memoized recursive function. I have recently done some subrange sums, but not in C.

for eg. if we need to find a sub array such that the (sum of the sub array) mod b is atleast equal to k, then what are the sort of functions that we can use?

Are all values positive, if not bow you define modulo for negative values?
How many values there are in array?
How big is b, how is range of values, are they random or for example typically small?

the values are positive. there can be around 50 values in the array. b can be anything between 1 and 1000000.

But i'm looking for a general algorithm that can be used for all functions not for this one specifically.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.