×

KCC03 - EDITORIAL

 0 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. This question is marked "community wiki". asked 18 Mar '18, 18:57 4★abhi55 42●6 accept rate: 5% 0★admin ♦♦ 19.8k●350●498●541

 0 @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. answered 19 Mar '18, 19:32 2.7k●1●6●18 accept rate: 10%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×3,820
×303
×13
×3

question asked: 18 Mar '18, 18:57

question was seen: 191 times

last updated: 21 Mar '18, 15:31