Given an array a[] on which, the following two types of inversions are performed:
- Count of pairs of indices (i, j) such that A[i] > A[j] and i < j
- Count of pairs of indices (i, j) such that A[i] > A[j] and j = i + 1
The task is to check if the count of both the inversions is equal or not. If they are equal, print “Yes”. Otherwise, print “No”.
Examples:
Input: a[] = {1, 0, 2}
Output: Yes
Explanation:
Count of inversion of Type 1 = 1 [(i, j) : (0, 1)]
Count of inversion of Type 2 = 1 [(i, j) : (0, 1)]
Input: a[] = {1, 2, 0}
Output: No
Explanation:
Count of inversion of Type 1 = 2 [(i, j) : (0, 2);(1, 2)]
Count of inversion of Type 2 = 1 [(i, j) : (1, 2)]
Approach:
To solve the problem, the difference between the two inversions need to be understood:
- For Type 2, if j = 5, then i can only be 4 as j = i + 1
- For Type 1, if j = 5, then i can be from 0 to 4, as i is less than j.
- Therefore, the inversion of Type 1 is basically an inversion of Type 2 summed up with all pair of indices(i, j) with i which is less than (j – 1) and a[i] > a[j].
- So, for any index j, the task is to check if there is index i, which is less than j – 1 and a[i] > a[j]. If any such pair of indices (i, j) is found, then print “No“. Otherwise, print “Yes“.
Below is the implementation of the above approach:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to check if the // count of inversion of two // types are same or not bool solve(int a[], int n) { int mx = INT_MIN; for (int j = 1; j < n; j++) { // If maximum value is found // to be greater than a[j], // then that pair of indices // (i, j) will add extra value // to inversion of Type 1 if (mx > a[j]) return false; // Update max mx = max(mx, a[j - 1]); } return true; } // Driver code int main() { int a[] = { 1, 0, 2 }; int n = sizeof(a) / sizeof(a[0]); bool possible = solve(a, n); if (possible) cout << "Yes" << endl; else cout << "No" << endl; return 0; } |
Java
// Java program to implement // the above approach import java.io.*;class GFG{ // Function to check if the // count of inversion of two // types are same or not static boolean solve(int a[], int n) { int mx = Integer.MIN_VALUE; for(int j = 1; j < n; j++) { // If maximum value is found // to be greater than a[j], // then that pair of indices // (i, j) will add extra value // to inversion of Type 1 if (mx > a[j]) return false; // Update max mx = Math.max(mx, a[j - 1]); } return true; } // Driver codepublic static void main (String[] args){ int a[] = { 1, 0, 2 }; int n = a.length; boolean possible = solve(a, n); if (possible) System.out.println("Yes"); else System.out.println("No"); }}// This code is contributed by offbeat |
Python3
# Python3 program to implement # the above approach import sys# Function to check if the # count of inversion of two # types are same or not def solve(a, n): mx = -sys.maxsize - 1 for j in range(1, n): # If maximum value is found # to be greater than a[j], # then that pair of indices # (i, j) will add extra value # to inversion of Type 1 if (mx > a[j]): return False # Update max mx = max(mx, a[j - 1]) return True# Driver code a = [ 1, 0, 2 ] n = len(a) possible = solve(a, n) if (possible != 0): print("Yes") else: print("No")# This code is contributed by sanjoy_62 |
C#
// C# program to implement // the above approach using System; class GFG{ // Function to check if the // count of inversion of two // types are same or not static bool solve(int[] a, int n) { int mx = Int32.MinValue; for(int j = 1; j < n; j++) { // If maximum value is found // to be greater than a[j], // then that pair of indices // (i, j) will add extra value // to inversion of Type 1 if (mx > a[j]) return false; // Update max mx = Math.Max(mx, a[j - 1]); } return true; } // Driver code public static void Main () { int[] a = { 1, 0, 2 }; int n = a.Length; bool possible = solve(a, n); if (possible) Console.WriteLine("Yes"); else Console.WriteLine("No"); } }// This code is contributed by sanjoy_62 |
Javascript
<script>// Javascript implementation of the above approach// Function to check if the // count of inversion of two // types are same or not function solve(a, n) { let mx = 0; for(let j = 1; j < n; j++) { // If maximum value is found // to be greater than a[j], // then that pair of indices // (i, j) will add extra value // to inversion of Type 1 if (mx > a[j]) return false; // Update max mx = Math.max(mx, a[j - 1]); } return true; } // Driver Code let a = [ 1, 0, 2 ]; let n = a.length; let possible = solve(a, n); if (possible) document.write("Yes"); else document.write("No");</script> |
Output:
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
