PERMWAR - EDITORIAL

editorial
,
1

PROBLEM LINK:

Practice Link

Author: Himanshu

DIFFICULTY:

EASY

PREREQUISITES:

Permutation

PROBLEM:

Given a value of n and a permutation which consist all the distinct values such that (1 <= ai <= n). Find out the maximum element wise remainder sum by choosing a permutation of your own following the condition that the permutation should have distinct values and (1 <= ai <= n).

QUICK EXPLANATION:

Key to AC: n * (n - 1) / 2

EXPLANATION:

The remainder of A divided by B is expressed as A mod B. If we express it as -

(1 mod 2) + (2 mod 3) +… + ((N1) mod N) + (N mod 1) = 1 + 2 + … + N1 =N * (N - 1) / 2

It is best to choose a permutation. This is explained below.

The selected permutation 1, 2, …, N just each 1 appeared one by times.
Suppose appears at the x ith position of the permutation . Then the objective function (the one we want to maximize ) is

(x1 mod 1) + (x2 mod 2) + ... + ( xN mod N)

When attention is paid to the sections at most each term is 0 , 1 , 2 , …, N - 1.
If xi = i − 1 and the remaining N is x 1 = N , then

(N mod 1) + (1 mod 2) + ... + ( (N − 1) mod N ) = 0 + 1 + 2 + ... + N − 1
Therefore, the maximum value of the objective function is N * (N - 1) / 2.

COMPLEXITY:

O(N)

SOLUTIONS:

Setter’s Solution