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

×

KCC03 - EDITORIAL

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

abhi55's gravatar image

4★abhi55
426
accept rate: 5%

edited 21 Mar '18, 15:31

admin's gravatar image

0★admin ♦♦
19.8k350498541


@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.

link

answered 19 Mar '18, 19:32

aryanc403's gravatar image

5★aryanc403
2.7k1618
accept rate: 10%

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:

×3,820
×303
×13
×3

question asked: 18 Mar '18, 18:57

question was seen: 191 times

last updated: 21 Mar '18, 15:31