## Friday, December 23, 2016

### Smallest number to multiply to convert floating point to natural - GeeksforGeeks

Smallest number to multiply to convert floating point to natural - GeeksforGeeks
Given a positive floating point number n, the task is to find the smallest integer k, such that when we multiply k with n, we get a natural number.

The idea is to convert given floating point number into a fraction (not necessarily in reduced form) and find the GCD of numerator and denominator. For example, if input floating point number is 30.25, we convert into fraction as 3025/100. This can be easily done by finding the position of dot.
Finally to get the answer, we divide the denominator of the converted fraction by GCD of denominator and numerator. For example, GCD of 3025 and 100 is 25. We divide 100 by 25 and get the answer as 4.

`int` `findnum(string &str)`
`{`
`    ``// Find size of string representing a`
`    ``// floating point number.`
`    ``int` `n = str.length();`

`    ``// Below is used to find denominator in`
`    ``// fraction form.`
`    ``int` `count_after_dot = 0;`

`    ``// Used to find value of count_after_dot`
`    ``bool` `dot_seen = ``false``;`

`    ``// To find numerator in fraction form of`
`    ``// given number. For example, for 30.25,`
`    ``// numerator would be 3025.`
`    ``int` `num = 0;`
`    ``for` `(``int` `i = 0; i < n; i++)`
`    ``{`
`        ``if` `(str[i] != ``'.'``)`
`        ``{`
`            ``num = num*10 + (str[i] - ``'0'``);`
`            ``if` `(dot_seen == ``true``)`
`                ``count_after_dot++;`
`        ``}`
`        ``else`
`            ``dot_seen = ``true``;`
`    ``}`

`    ``// If there was no dot, then number`
`    ``// is already a natural.`
`    ``if` `(dot_seen == ``false``)`
`       ``return` `1;`

`    ``// Find denominator in fraction form. For example,`
`    ``// for 30.25, denominator is 100`
`    ``int` `dem = (``int``)``pow``(10, count_after_dot);`

`    ``// Result is denominator divided by`
`    ``// GCD-of-numerator-and-denominator. For example, for`
`    ``// 30.25, result is 100 / GCD(3025,100) = 100/25 = 4`
`    ``return` `(dem / gcd(num, dem));`
`}`