You are not logged in. Please login at www.codechef.com to post your questions!

×

Help in this codeforces question

The following question was asked in VK Cup Wild Card Round 1 Contest organised by codeforces. My code gives Time limit Exceeded error...Please help me out to optimise my solution.

Here is the problem: There are n points on a straight line, and the i-th point among them is located at Xi. All these coordinates are distinct.

Determine the number m — the smallest number of points you should add on the line to make the distances between all neighboring points equal. Also it is given that the position Xi of ith point lies between -10^9 to 10^9.

Here is the link to my code:

http://codeforces.com/contest/926/submission/36411390

The link to the original question is:

http://codeforces.com/contest/926/problem/B

asked 19 Mar '18, 21:15

puru12's gravatar image

3★puru12
1
accept rate: 0%

converted to question 19 Mar '18, 22:15

vijju123's gravatar image

4★vijju123 ♦♦
15.4k12066


When i solved this problem i come up with the same approach and you know what it got accepted in #234ms (In GNU C++ 14 Lang with gcd recursive version and with integer types )

Key Points for code optimization are:

  1. Change long integers to integers. (as operation on long integers are more costly than integers )
  2. Changing recursive gcd() function to iterative might reduce some time. (as far as i know recursive version and iterative version both have same time complexity but recursive calls overhead can be avoided in iterative version)
link

answered 19 Mar '18, 23:29

mohit_yadav389's gravatar image

2★mohit_yadav389
903
accept rate: 25%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,718
×678
×637

question asked: 19 Mar '18, 21:15

question was seen: 186 times

last updated: 19 Mar '18, 23:29