Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Byang and Kochuripana Trouble

Limits: 1s, 512 MB

Byang is the chief software engineer at Toad Incorporated. His grandmother is planning to give him a visit. But his grandmother is old and weak. She walks very slowly and cannot take long footsteps anymore. And most importantly, she hates “Kochuripana”.

Byang discovered that the only road to his house has some “Kochuripana”. He took notes on where the “Kochuripanas” are located. Then he passed the notes to you and told you that his grandmother always takes equal sized footsteps. Byang wonders what is the minimum length of footstep his grandmother can take so that she does not have to step on any “Kochuripana”. Now it is your job to find the answer.

Let’s denote positive X-axis as the only road to Byang’s house. Byang’s grandmother will start to walk from point 0. There are N “Kochuripanas” at integer points X1, X2,…., XN. You have to find the minimum length of footstep Byang’s grandmother can take so that she does not step on any “Kochuripana”. Note that, if Byang’s grandmother takes footsteps of size k, then she will step on these points:0, k, 2k, 3k, 4k… Also note that, Byang’s grandmother always takes footsteps of integer length.


On the first line a positive integer N (N <= 106)

On the next N lines there will be one integer Xi (1 <= Xi <= 107).


Only one line with one integer, the minimum length of footstep Byang’s grandmother should take to avoid “Kochuripana”.



  • himuhasib's Avatar


    Hasib is passionate about sport programming and artificial intelligence. He was an IOI participant through years 2013-2015. He qualified to ACM-ICPC World Finals 2016. He studies at North South University.