Problem link:
Practice
Contest link
Author: Vinay Kushwaha
Tester: Ujjawal Gupta
Editorial: Vinay Kushwaha
Difficulty:
Easy
Prerequisite:
Basic Maths, C++ stl.
Problem Statement :-
In this problem you are given two integers n and k and all the numbers are arranged in a circle in order 1 to n (in clockwise direction) . You have to choose two numbers at index i and j such that j=i+1 if i<n and j=1 if i=n . If a[i]<a[j] you have to do a[i]=a[j]%k.
Algorithm:-
If we observe the question carefully we can see that all the numbers are arranged in ascending order except the indexes i=n and j=1 So if we start taking mod with we will get a pattern like [2,3,…,0,1,2,3,…0,…n] if k>1 and if k=1 it will be [0,0,0,…n].
For k=1 we can do
ans=n
For k>1
We can see the the part [2,3,…0] will repeat (n/k) times
so we can find the sum of that part using
k–;
sum_k=(k*(k+1)/2);
sum=(sum_k*(n/k));
and the remaining part sum by
rem=n%k
sum_rem=(rem*(rem+1)/2);
ans=sum_rem+sum_part
at last we have to subtract -1 from the ans because we are not getting -1 in starting and +n in the answeer for i=n and j=1.