< Back to forum

Let Us Understand Computer

in this problem i could understand how to approach.anyone plzz explain me how to solve this problem

Asked by: Suraj_Modi on April 7, 2019, 1:04 p.m. Last updated on April 7, 2019, 1:04 p.m.


Enter your answer details below:


Preview

Enter your comment details below:

Preview




1 Answer(s)

avatar

problem link :)

we are using the fact that for any given 'D', we have a minimum value of divisor say x that will not give overflow and also all the values greater than this value not give overflow, and all the values less than this give overflow. So, we need to run a binary search over range 1...D and find the value of x and then answer is (n-x+1) except when the value of 'D' is 1. the time complexity of the algorithm is O(log^2(n)) for each test case. we can also solve the problem in O(log(n)) time but this requires some generalization and bit manipulation.

rishup132 last updated on April 7, 2019, 1:04 p.m. 0    Reply    Upvote   

Instruction to write good question
  1. 1. Write a title that summarizes the specific problem
  2. 2. Pretend you're talking to a busy colleague
  3. 3. Spelling, grammar and punctuation are important!

Bad: C# Math Confusion
Good: Why does using float instead of int give me different results when all of my inputs are integers?
Bad: [php] session doubt
Good: How can I redirect users to different pages based on session data in PHP?
Bad: android if else problems
Good: Why does str == "value" evaluate to false when str is set to "value"?

Refer to Stack Overflow guide on asking a good question.