How Do I Write the Code for Dividing an Even Number with Biggest Equal Odd Numbers
I Have a Set of Numbers to Check. If the Number Is Even, the Program Will Check the Biggest Odd Dividers of It Which Are Equal. for Example, If the Number Is...
I have a set of numbers to check. if the number is even, the program will check the biggest odd dividers of it which are equal. For example, if the number is 12, program will return an array like [3,3,3,3] or for 36, it will be [9,9,9,9] and let's say for 54, [27, 27] and 56, [7,7,7,7,7,7,7,7] and so on. I am writing my code in ruby. I couldn't figure out how to write the correct algorithm. Any help will be appreciated.
2 Answers
Try this
def fun(num)
odd = num
odd /= 2 while odd.even?
[odd] * (num / odd)
end
How does this work?
This divides num by 2 until it is an odd number.
You can do this in two steps:
Determining the number of times the number is divisible by two (assuming in is positive) - in pseudocode:
int divisors(int in):
int divisor = 1
for(; in % 2 == 0; divisor *= 2)
in /= 2 //integer division!!!
return divisor
divisors will return the largest power of two, by which in is evenly divisible. The idea is that any number n can be represented by it's prime-factorization, which is something like:
n = 2^a * 3^b * 5^c * ...
We only need to know a, as the rest of the factorization will necessarily be our largest odd divisor. Or in a bit more detail:
n = 2^a * 3^b * 5^c * ...
largest_odd_divisor = 3^b * 5^c * ...
largest_even_divisor = 2^a = divisors(n)
We can't find any larger odd divisor, since we only eliminated all even divisors from n, so we only got even divisors that we could add to largest_odd_divisor, but due to this the divisor would turn even.
The rest is trivial:
Get a (as shown above), create an array of size 2^a and fill it up with n / (2^a).
Maya is a hardware enthusiast who tests and reviews smart home devices, smartphones, wearables, and audio gear. She focuses on practical consumer value and build quality.
