Created
March 5, 2020 20:42
-
-
Save Mando75/a0a87d1ec3874334f1e1fd246bbb1471 to your computer and use it in GitHub Desktop.
RAVI
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def find_ravi_pairs_in_bound(n) | |
ravis = [] | |
# Just setting an upper bound on this for now | |
(1..(n/2)).each do |i| | |
(i..n).each do |j| | |
# Add the two numbers together and convert them to binary string | |
a = (i + j).to_s(2) | |
# Multiply the two numbers together and convert them to binary string | |
b = (i * j).to_s(2).reverse | |
# just working with the upper bound | |
break if i * j > n | |
# the reversed string b could have a bunch of leading zeros which | |
# would not be present in a. We trim these zeros so we can compare | |
# (leading zeros in a binary string don't matter) | |
b = trim_zeros(b) | |
if a == b | |
# We found a pair, add them to the array | |
ravis.push([i, j]) if a == b | |
end | |
end | |
end | |
return ravis | |
end | |
# Removes leading zeros from a binary string | |
def trim_zeros(bin_string) | |
# Get the index of the first one | |
zero_pad_index = bin_string.index('1') | |
# remove all the zeros up to the leading one | |
return bin_string.slice(zero_pad_index, bin_string.length) | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment