To find all the expressions of a given sequence which evaluate to a given value k

Please look at the following link for the problem
http://geeksforgeeks.org/forum/topic/yahoo-interview-question-for-software-engineerdeveloper-fresher-about-algorithms-9

#!/usr/bin/env ruby

#The recursive function to find out all the expressions which evaluate to a given value
#The technique used is "backtracking"

def findExpr(s, expr, k)
if s.length != 0
expr += s[0].chr
val = eval(expr)

if val == k && s.length == 1
print expr, "\n"
elsif val < k
            #The operations supported are '*', '+' and '.'
            #where '.' is simple concatenation of the digits
findExpr(s[1..-1], expr + '*', k)
findExpr(s[1..-1], expr + '+', k)
findExpr(s[1..-1], expr, k)
end
end
end

findExpr("123456789", "", 2097)
Advertisements

One thought on “To find all the expressions of a given sequence which evaluate to a given value k

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s