CODEWITHSUNDEEP
rubylogical-operators
nikhil
nikhil

Reputation: 9385

Understanding Ruby logical operators

I'm new to Ruby and thought that it would be a great way to learn more by solving the problems at Project Euler.

Here's what I came up with using brute force for Problem 5:

#What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
end_point = 1_000_000_000 
start_point = 2_520
(start_point..end_point).each do |number|
  flag = true
  (2..20).each do |divisor|
    flag = flag & ( number % divisor ) == 0 ? true : false
    end
  print number.to_s + "\n" if flag
end

This runs for a long time and gives no answer.

Then I used the same logic to write a C++ program to do the same task:

#include<iostream>

using namespace std;

int main()
{
  unsigned long int solution = 2520;
  while(1)
  {
    bool flag = true;
    for(int divisor=2;divisor<=20;divisor++)
    {
      if( solution % divisor == 0)
        flag = flag & true;
      else{
        flag = false;
        break;
      }
    }
    if(flag == true){
      cout<<solution<<endl;
      break;
    }
    solution++;
  }
  return 0;
}

This one gives me the correct solution and runs for barely a second. The execution time doesn't really concern me as Ruby is interpreted and C++ compiled but Ruby's failure at returning the correct answer does surprise me. I think it might be because of me trying to write C++ Ruby style and not the actual Ruby way.

What am I doing wrong here?

Upvotes: 0

Views: 774

Answers (2)

Dhruva Sagar
Dhruva Sagar

Reputation: 7307

I actually solved this problem without writing a program for it. This is the logic I used :

Write down all prime numbers less than 20 (target).

[2, 3, 5, 7, 11, 13, 17, 19]

For each prime number, raise it to the maximum power for which it is lesser than the target (20).

2**4 * 3**2 * 5 * 7 * 11 * 13 * 17 * 19

For doing it programmatically use the Sieve of Eratosthenes - http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes algorithm for iterating over the prime numbers. For each prime number in the list, find the maximum power to which it is raised to get a number lesser than the target (20). You can find the power using this formula : (Math.log(target)/Math.log(i)).floor

Assuming you get the array of primes : nums = [2, 3, 5, 7, 11, 13, 17, 19]

Then you can get the answer easily by using this :

nums.map {|i| i**((Math.log(target)/Math.log(i)).floor)}.inject(:*)

Upvotes: 3

Chowlett
Chowlett

Reputation: 46667

Note: I have not run either of the proposed solutions below to completion - they still take a long time - so correctness is not guaranteed!

The line where you update flag is the problem. You're using & (bitwise-and) rather than && (Boolean-and).

Among other problems, & has higher operator precedence than ==, so your line is interpreted as (since ? true : false is redundant):

flag = (flag & (number % divisor)) == 0

Now, it appears that true & some_integer is true, which is not == 0, so flag is always set to false.

Instead, you want:

flag = flag && (number % divisor == 0)

or, more succinctly and Rubyish:

flag &&= number % divisor == 0

An alternative solution would be to do:

i = 1
while true
  break unless (2..20).any? {|d| i % d != 0}
  i+=1
end
puts i

Upvotes: 2

Related Questions