INUM - Interesting Numbers

no tags 

Jack and Jill went up the hill. Jack proposed Jill after reaching at the top of the hill. Jill gave Jack 'N' numbers and asked him to choose a pair of numbers such that their absolute difference is minimum. She also asked him to choose a pair of numbers such that their absolute difference is maximum. Jill wondered just finding maximum and minimum values is mainstream and it will be a cakewalk for Jack, instead she asked him to find number of pairs which have minimum absolute difference and number of pairs which have maximum absolute difference.

Jill will accept Jack's proposal only if he can answer her question correctly. Jack does not know programming. Fortunately Jack had his laptop with him, fully charged and with good internet connection. He mailed you the numbers and asked you to mail him the answers back, as you are known to be a good programmer. Now it's your turn to help him.

Input Format
First line contains a positive integer 'N'.
Next line contains 'N' non-negative integers 'a[i]' separated by a single space.

Output Format
Print the number of pairs having minimum and maximum difference separated by a single space.

1 ≤ N ≤ 105
0 ≤ a[i] ≤ 1015

Sample Input
5 12 8 1 35

Sample Output
1 1

It's optimal to choose the pair (5, 8) for the minimum difference.So only 1 pair.
It's optimal to choose the pair (1,35) for the maximum difference. Here also only 1 pair.

hide comments
Snarl_jsb: 2016-04-26 06:51:47

The problems say 1 ≤ N ≤ 10^5,but if we use int,we will get WA,Why?

kartikay singh: 2015-08-27 07:43:35

nice question..Used MAP :D
AC in 1 go !!

Last edit: 2015-08-27 07:44:02
:.Mohib.:: 2015-06-09 04:29:32

Thnx @shashank ur cmnt help me....nice que!!

Shashank Tiwari: 2015-06-09 03:58:18

Let me explain this question ....

You have to find NUMBER OF PAIRS i.e. (a[i],a[j]) such that i<j satisfying max and min differences as mentioned in question. Following test cases might help u understand the question ....
Test case 1 :

1 1 1 1 1
ans = 10 10
Test case 2

1 1 1 2 2
ans = 4 6

Test case 3

ans = 0 0

1 2 3 4 5
ans = 4 1

Please make sure to use long long everywhere . If you use int somewhere in question , then it might be involved in some product which should not result overflow as indexes can go upto 10^5 and their product can go upto 10^10. (yes, they will be multiplied somewhere !! )


ashish jaiswal: 2015-03-23 20:03:31

what wrong in my code??
plz check all my test cases are runnuing perfectly still it's showing wrong answer..

Last edit: 2015-03-30 20:05:27
Raghav Aggiwal: 2014-10-17 14:13:46

8 Wa just because of taking one value in int instead of long long int .. BE CAREFUL

Hasil Sharma: 2014-10-07 15:00:34

@Aayush if it is total number of pairs, just like you said. Don't you think the sample input in incorrect ?

Is it like pair that pair (a[i],a[j]) for any difference should have condition j>i true ? This isn't clear from problem description, please clarify

DEEPANSHU JAIN: 2014-09-28 20:20:12

you should clearly mention whether in the pair (ar[i],ar[j]),i<=j, or n>=2..

EDIT : It is implicit that here pair refers to unordered pair ( i<j ) , and problem statement is correct .

Last edit: 2014-09-29 08:26:48
DEEPANSHU JAIN: 2014-09-28 20:18:45

Poor problem statement!!

shiv prasad chabarval: 2014-09-28 11:13:34

@Aayush Agarwal please check why i am getting WA. i think my logic is right

Added by:Aayush Agarwal
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem used for codecracker , co-authored by Rana Saha