Interesting Subarray Codechef Java Solution (SUBARRY)

Problem

• You are given an array A of length N.

• The interesting value of a subarray is defined as the product of the maximum and minimum elements of the subarray.

• Find the minimum and maximum interesting value over all subarrays for the given array.

• Note: A subarray is obtained by deletion of several (possibly zero) elements from the beginning of the array and several (possibly zero) elements from the end of the array.

Input Format

• The first line of input will contain a single integer T, denoting the number of test cases.
• The first line of each test case contains an integer N- the length of the array A.
• The second line of each test case contains N space-separated integers A1,A2,...AN .

Output Format

• For each test case, output two space-separated integers on a new line the minimum and maximum interesting value over all subarrays for the given array.

Constraints

• $1\le T\le 100$
• $1 \leq N \leq 10^5$
• $-10^9 \leq A_i \leq 10^9$
• The sum of $N$ over all test cases won't exceed $3 \cdot 10^5$.

Input

• 2 2 2 2 3 5 0 9

Output

• 4 4 0 81

Explanation:

Test case $1$: The minimum interesting value possible is $4$. A subarray with an interesting value equal to $4$ is $[2,2]$. Here, both minimum and maximum elements of the subarray are $2$. It can be proven that no subarray of the array has interesting value less than $4$.
The maximum interesting value possible is $4$. A subarray with an interesting value equal to $4$ is $[2,2]$. Here, both minimum and maximum elements of the subarray are $2$. It can be proven that no subarray of the array has interesting value greater than $4$.

Test case $2$: The minimum interesting value possible is $0$. A subarray with interesting value equal to $0$ is $[5, 0, 9]$. Here, minimum element is $0$ and maximum element is $9$. It can be proven that no subarray of the array has interesting value less than $0$.
The maximum interesting value possible is $81$. A subarray with interesting value equal to $81$ is $[9]$. Here, both minimum and maximum elements of the subarray are $9$. It can be proven that no subarray of the array has interesting value more than $81$.

/* package codechef; // don't place package name! */ import java.util.*; import java.lang.*; import java.io.*; import java.util.Arrays; /* Name of the class has to be "Main" only if the class is public. */ class Codechef { public static void main (String[] args) throws java.lang.Exception { try { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); while(t>=1 && t<=100) { int n = sc.nextInt(); long[] arr = new long[n]; for (int i=0;i<n;i++) { arr[i] = sc.nextInt(); } Arrays.sort(arr); long min = Integer.MAX_VALUE; long max = Integer.MIN_VALUE; //max product value for the maximum of array max = Math.max((arr[0]*arr[0]),arr[(int) (n-1)]*arr[(int) (n-1)]); //for minimum product if(arr[0]<=0 && arr[(int) (n-1)]>0) { min = arr[0]*arr[(int) (n-1)]; }else if(arr[0]>=0) { min = arr[0]*arr[0]; }else{ min = arr[(int) (n-1)]*arr[(int) (n-1)]; } System.out.println(min+" "+max); } } catch(Exception e) { return; } } }

Read More

Good Pairs Codechef Java Solution (EQPAIR)

Problem

• You are given an array A of length N.

A pair $(i, j)$ $(1\le i\lt j \le N)$ is said to be good if $gcd(A_i, A_j) = lcm(A_i, A_j)$. Here $gcd$GCD denotes the greatest common divisor and $lcm$LCM denotes  Least Common Multiple

• Find the total number of good pairs present in the given array.

Input Format

• The first line of input will contain a single integer T, denoting the number of test cases.

• The first line of each test case contains an integer N- the length of the array A.

• The second line of each test case contains N space-separated integers A1,A2,....AN

Output Format

• For each test case, output on a new line the total number of such good pairs possible in the given array.

Constraints

• $1\le T\le 100$
• $1 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$
• The sum of $N$ over all test cases won't exceed $3 \cdot 10^5$.

Input 

• 5 2 5 9 5 1 5 5 5 9 8 2 5 5 2 9 9 9 12 4 12 12 18 18 5 12 15 10 5 9

Output

• 0 3 5 2 0

Explanation:

Test case $1$: No good pair is present.

Test case $2$: The good pairs $(i, j)$ are: $(2, 3), (3, 4),$ and $(2, 4)$. To elaborate, $gcd(A_2, A_3) = lcm(A_2, A_3) = 5$.

Test case $3$: The good pairs $(i, j)$ are: $(1, 4), (2, 3), (5, 6), (6, 7),$ and $(5, 7)$. To elaborate, $gcd(A_1, A_4) = lcm(A_1, A_4) = 2$.

Test case $4$: The good pair $(i, j)$ are: $(1, 2),$ and $(3, 4)$. To elaborate, $gcd(A_3, A_4) = lcm(A_3, A_4) = 18$.

Test case $5$: No good pair is present.

/* package codechef; // don't place package name! */ import java.util.*; import java.lang.*; import java.io.*; /* Name of the class has to be "Main" only if the class is public. */ class Codechef { public static void main (String[] args) throws java.lang.Exception { try { Scanner sc = new Scanner(System.in); long t = sc.nextInt(); HashMap<Long,Long> map = new HashMap<>(); while(t>=1 && t<=1000) { int n = sc.nextInt(); long a[] = new long[n]; for (int i=0;i<n ;i++ ) { a[(int) i] = sc.nextInt(); } for (int i=0;i<n ;i++ ) { if(map.containsKey(a[i])) { map.put(a[i],map.get(a[i])+1); } else{ map.put(a[i], (long) 1); } } long sum=0; for(Map.Entry e : map.entrySet()) { Long k = (Long)e.getValue(); if(k>1) { sum = sum +(k*(k-1))/2; } } System.out.println(sum); map.clear(); } } catch(Exception e) { return; } } }

Read More