KCC03 - EDITORIAL

easy
externalcontest
kcc03
kcct2018

#1

DIFFICULTY:
EASY

PREREQUISITES:
Modulus Operator , Linear Search

PROBLEM:

 We have to find the maximum modulus of a pair of number from an array.

Explanation:

1) Naive Approach: 

      We can compute the modulo function for every possible pair of elements in an array of size N with a complexity of O(N^2).
      
      Pseudo Code :
       
          maxmodulo=0;
          for i in range 0 to n-1:
		    for j in range i+1 to n-1:
			    if max(i,j)%min(i,j)>maxmodulo :
				   maxmodulo=max(i,j)%min(i,j);
                end if
            end for
          end for
		  
	  Time Complexity : O(N^2)
	  But this approach will fail as N <= 10^6 and it will give a TLE (Time Limit Exceed) Error.

2) Optimized Approach :

      One can easily compute the result by taking modulo operator over the second largest and the largest element of the array.

           Result = Second_Largest_Element % Largest_Element		  
     
	 Time Complexity : O(N);

Editorialist’s Solution:
Can be found here.


#2

@abhi55 @srvptk I would like to report to @admin @vijju123 that for this external contest https://www.codechef.com/KCCT2018 third problem https://www.codechef.com/KCCT2018/problems/KCC03 is repeated ans was already available on codechef on https://www.codechef.com/IOPC2017/problems/IOPC17C and I hope organizers and codechef admin will look into this issue before awarding any prizes.