How to optimize traversing a range of numbers?

by

You should not optimize the traversal, you should eliminate it. Counting one-by-one is slow, so you need to come up with a mathematical formula to produce the count without a loop.

Fortunately, it is not too hard: you start from s, and you add one m times, mod n. Hence, you could compute (s-1) % n and (m-1) % n, add them together, take % n on the final result, and add 1 to convert zero-based result to one-based:

(((s-1) % n) + ((m-1) % n)) % n + 1

Demo.

* Subtract one from s because s is one-based.
** Subtract one from m because the first item is distributed to the initial prisoner.

More Related Contents:

  1. Should a class be thread-safe? [closed]
  2. C++ while loop resetting variables?
  3. comparison operator in for loop in c++ [closed]
  4. What is a lambda expression in C++11?
  5. How to print (using cout) a number in binary form?
  6. Initialize static variables in C++ class?
  7. What is the correct way of using C++11’s range-based for?
  8. How can I efficiently select a Standard Library container in C++11?
  9. What is the most effective way to get the index of an iterator of an std::vector?
  10. What is the size of void?
  11. “invalid use of incomplete type” error with partial template specialization
  12. Meaning of = delete after function declaration
  13. How to Generate a calling graph for C++ code
  14. Create an array when the size is a variable not a constant
  15. Appending a vector to a vector [duplicate]
  16. Iterating over a struct in C++
  17. How expensive is RTTI?
  18. Calling virtual function from destructor
  19. Is a return statement mandatory for C++ functions that do not return void?
  20. OpenCV unable to set up SVM Parameters
  21. request for member `…’ is ambiguous in g++
  22. Does C++ contain the entire C language? [duplicate]
  23. Do you (really) write exception safe code? [closed]
  24. How to use glOrtho() in OpenGL?
  25. The new keyword “auto”; When should it be used to declare a variable type? [duplicate]
  26. C++: how to get fprintf results as a std::string w/o sprintf
  27. Why am I able to make a function call using an invalid class pointer
  28. Member function with static linkage
  29. How to find Longest Common Substring using C++
  30. Are there any downsides to using UPX to compress a Windows executable?

Leave a Comment