Given two arrays A and B of size N. Array A is in increasing order and B is in decreasing order. Both arrays are the subsequences of the numbers from 1 to 2N. The task is to find the sum of the absolute difference of two arrays.
Sum = |A1 – B1| + |A2 – B2| + |A3 – B3| + …. + |AN – BN|
Examples:
Input : A[] = {1, 2, 3, 4, 5}, B[] = {10, 9, 8, 7, 6}
Output : 25
Input : A[] = {1, 5, 6, 8, 10, 12}, B[] = {11, 9, 7, 4, 3, 2}
Output : 36
Naive Approach: A naive approach is to run a loop and find the sum of the absolute differences.
Efficient Approach: Proizvolov’s identity is an identity concerning sums of the differences of positive integers. It states that if we take first 2N integers and partition them into two subsets of N numbers each.
Arrange one subset in increasing order : A1 < A2 < A3 < …. < AN
Arrange another subset in decreasing order : B1 > B2 > B3 > …. > BN
Then the sum |A1 – B1| + |A2 – B2| + |A3 – B3| + …. + |AN – BN| is always equals to N2
Below is the implementation of the above approach:
C++
// CPP program to implement proizvolov's identity#include<bits/stdc++.h>using namespace std;// Function to implement proizvolov's identityint proizvolov(int a[], int b[], int n){ // According to proizvolov's identity return n*n;}// Driver codeint main(){ int a[] = {1, 5, 6, 8, 10}, b[] = {9, 7, 4, 3, 2}; int n = sizeof(a) / sizeof(a[0]); // Function call cout << proizvolov(a, b, n); return 0;} |
Java
// Java program to implement proizvolov's identityclass GFG{ // Function to implement proizvolov's identity static int proizvolov(int a [], int b [], int n) { // According to proizvolov's identity return n * n; } // Driver code public static void main (String[] args) { int a [] = {1, 5, 6, 8, 10}; int b [] = {9, 7, 4, 3, 2}; int n = a.length; // Function call System.out.println(proizvolov(a, b, n)); }}// This code is contributed by ihritik |
Python3
# Python3 program to implement# proizvolov's identity# Function to implement # proizvolov's identitydef proizvolov(a, b, n): return n * n# Driver codea = [ 1, 5, 6, 8, 10 ] b = [ 9, 7, 4, 3, 2 ] n = len(a) # Function callprint(proizvolov(a, b, n, )) # This code is contributed by nidhiva |
C#
// C# program to implement proizvolov's identityusing System;class GFG{ // Function to implement proizvolov's identity static int proizvolov(int [] a, int [] b, int n) { // According to proizvolov's identity return n * n; } // Driver code public static void Main () { int [] a = {1, 5, 6, 8, 10}; int [] b = {9, 7, 4, 3, 2}; int n = a.Length; // Function call Console.WriteLine(proizvolov(a, b, n)); }}// This code is contributed by ihritik |
Javascript
<script>// Javascript program to implement // proizvolov's identity// Function to implement proizvolov's identityfunction proizvolov(a, b, n){ // According to proizvolov's identity return n*n;}// Driver code let a = [1, 5, 6, 8, 10], b = [9, 7, 4, 3, 2]; let n = a.length; // Function call document.write(proizvolov(a, b, n));</script> |
25
Time complexity: O(1) because constant operations are done
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
