Statistics

Problem Statement for "FibonacciDiv2"

Problem Statement

The Fibonacci sequence is defined as follows:
  • F[0] = 0
  • F[1] = 1
  • for each i >= 2: F[i] = F[i-1] + F[i-2]
Thus, the Fibonacci sequence starts as follows: 0, 1, 1, 2, 3, 5, 8, 13, ... The elements of the Fibonacci sequence are called Fibonacci numbers.

You're given an int N. You want to change N into a Fibonacci number. This change will consist of zero or more steps. In each step, you can either increment or decrement the number you currently have. That is, in each step you can change your current number X either to X+1 or to X-1.

Return the smallest number of steps needed to change N into a Fibonacci number.

Definition

Class:
FibonacciDiv2
Method:
find
Parameters:
int
Returns:
int
Method signature:
int find(int N)
(be sure your method is public)

Constraints

  • N will be between 1 and 1,000,000, inclusive.

Examples

  1. 1

    Returns: 0

    The number 1 is already a Fibonacci number. No changes are necessary.

  2. 13

    Returns: 0

    The number 13 is also a Fibonacci number.

  3. 15

    Returns: 2

    The best way to change 15 into a Fibonacci number is to decrement it twice in a row (15 -> 14 -> 13).

  4. 19

    Returns: 2

    You can increase it by 2 to get 21.

  5. 1000000

    Returns: 167960

    This is the biggest possible number that you can get as input.

  6. 999999

    Returns: 167959

  7. 514229

    Returns: 0

  8. 673134

    Returns: 158905

  9. 199

    Returns: 34

  10. 100

    Returns: 11

  11. 200

    Returns: 33

  12. 300

    Returns: 67

  13. 400

    Returns: 23

  14. 500

    Returns: 110

  15. 567876

    Returns: 53647

  16. 257

    Returns: 24

  17. 765

    Returns: 155

  18. 9368

    Returns: 1578

  19. 2615

    Returns: 31

  20. 2

    Returns: 0

  21. 27491

    Returns: 1166

  22. 5

    Returns: 0

  23. 7

    Returns: 1

  24. 8

    Returns: 0

  25. 12

    Returns: 1

  26. 15

    Returns: 2

  27. 16

    Returns: 3

  28. 19

    Returns: 2

  29. 18

    Returns: 3

  30. 3417

    Returns: 764

  31. 28

    Returns: 6

  32. 34

    Returns: 0

  33. 35

    Returns: 1

  34. 1728

    Returns: 131

  35. 2003

    Returns: 406

  36. 142178

    Returns: 20785

  37. 125784

    Returns: 4391

  38. 59876

    Returns: 13508

  39. 606259

    Returns: 92030

  40. 165

    Returns: 21

  41. 76856

    Returns: 1831

  42. 24564

    Returns: 4093

  43. 26377

    Returns: 2280

  44. 290

    Returns: 57

  45. 186312

    Returns: 10106

  46. 3299

    Returns: 715

  47. 707233

    Returns: 124807

  48. 16181

    Returns: 1530

  49. 536

    Returns: 74

  50. 758092

    Returns: 73948

  51. 190039

    Returns: 6379

  52. 219

    Returns: 14

  53. 18208

    Returns: 497

  54. 874

    Returns: 113

  55. 1281

    Returns: 294

  56. 212428

    Returns: 16010

  57. 29088

    Returns: 431

  58. 165003

    Returns: 31415

  59. 982

    Returns: 5

  60. 507547

    Returns: 6682

  61. 127

    Returns: 17

  62. 320087

    Returns: 2276

  63. 487803

    Returns: 26426

  64. 183288

    Returns: 13130

  65. 9

    Returns: 1

  66. 4

    Returns: 1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: