Sum of absolute differences of pairs from the given array that satisfy the given condition
Given an array arr[] of N elements, the task is to find the sum of absolute differences between all pairs (arr[i], arr[j]) such that i < j and (j – i) is prime.
Example:
Input: arr[] = {1, 2, 3, 5, 7, 12}
Output: 45
All valid index pairs are:
(5, 0) -> abs(12 – 1) = 11
(3, 0) -> abs(5 – 1) = 4
(2, 0) -> abs(3 – 1) = 2
(4, 1) -> abs(7 – 2) = 5
(3, 1) -> abs(5 – 2) = 3
(5, 2) -> abs(12 – 3) = 9
(4, 2) -> abs(7 – 3) = 4
(5, 3) -> abs(12 – 5) = 7
11 + 4 + 2 + 5 + 3 + 9 + 4 + 7 = 45
Input: arr[] = {2, 5, 6, 7}
Output: 11
Approach: Initialise sum = 0 and run two nested loops and for every pair arr[i], arr[j] is (j – i) is prime then update the sum as sum = sum + abs(arr[i], arr[j]). Print the sum in the end.
Below is the implementation of the above approach:
// C++ implementation of the approach
#include <iostream>
using namespace std;
// Function that returns true
// if n is prime
bool isPrime(int n)
{
// Corner case
if (n <= 1)
return false;
// Check from 2 to n-1
for (int i = 2; i < n; i++)
if (n % i == 0)
return false;
return true;
}
// Function to return the absolute
// differences of the pairs which
// satisfy the given condition
int findSum(int arr[], int n)
{
// To store the required sum
int sum = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++)
// If difference between the indices
// is prime
if (isPrime(j - i)) {
// Update the sum with the absolute
// difference of the pair elements
sum = sum + abs(arr[i] - arr[j]);
}
}
// Return the sum
return sum;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3, 5, 7, 12 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findSum(arr, n);
return 0;
}
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function that returns true
// if n is prime
static boolean isPrime(int n)
{
// Corner case
if (n <= 1)
{
return false;
}
// Check from 2 to n-1
for (int i = 2; i < n; i++)
{
if (n % i == 0)
{
return false;
}
}
return true;
}
// Function to return the absolute
// differences of the pairs which
// satisfy the given condition
static int findSum(int arr[], int n)
{
// To store the required sum
int sum = 0;
for (int i = 0; i < n - 1; i++)
{
// If difference between the indices is prime
for (int j = i + 1; j < n; j++)
{
if (isPrime(j - i))
{
// Update the sum with the absolute
// difference of the pair elements
sum = sum + Math.abs(arr[i] - arr[j]);
}
}
}
// Return the sum
return sum;
}
// Driver code
public static void main(String[] args)
{
int arr[] = {1, 2, 3, 5, 7, 12};
int n = arr.length;
System.out.println(findSum(arr, n));
}
}
// This code is contributed by Rajput-Ji
# Python3 implementation of the approach
# Function that returns true
# if n is prime
def isPrime(n) :
# Corner case
if (n <= 1) :
return False;
# Check from 2 to n-1
for i in range(2, n) :
if (n % i == 0) :
return False;
return True;
# Function to return the absolute
# differences of the pairs which
# satisfy the given condition
def findSum(arr, n) :
# To store the required sum
sum = 0;
for i in range(n - 1) :
for j in range(i + 1, n) :
# If difference between the indices
# is prime
if (isPrime(j - i)) :
# Update the sum with the absolute
# difference of the pair elements
sum = sum + abs(arr[i] - arr[j]);
# Return the sum
return sum;
# Driver code
if __name__ == "__main__" :
arr = [ 1, 2, 3, 5, 7, 12 ];
n = len(arr);
print(findSum(arr, n));
# This code is contributed by AnkitRai01
// C# implementation of the approach
using System;
class GFG
{
// Function that returns true
// if n is prime
static bool isPrime(int n)
{
// Corner case
if (n <= 1)
{
return false;
}
// Check from 2 to n-1
for (int i = 2; i < n; i++)
{
if (n % i == 0)
{
return false;
}
}
return true;
}
// Function to return the absolute
// differences of the pairs which
// satisfy the given condition
static int findSum(int []arr, int n)
{
// To store the required sum
int sum = 0;
for (int i = 0; i < n - 1; i++)
{
// If difference between the indices is prime
for (int j = i + 1; j < n; j++)
{
if (isPrime(j - i))
{
// Update the sum with the absolute
// difference of the pair elements
sum = sum + Math.Abs(arr[i] - arr[j]);
}
}
}
// Return the sum
return sum;
}
// Driver code
public static void Main(String[] args)
{
int []arr = {1, 2, 3, 5, 7, 12};
int n = arr.Length;
Console.WriteLine(findSum(arr, n));
}
}
// This code is contributed by PrinciRaj1992
<script>
// JS implementation of the approach
// Function that returns true
// if n is prime
function isPrime(n)
{
// Corner case
if (n <= 1)
return false;
// Check from 2 to n-1
for (let i = 2; i < n; i++)
if (n % i == 0)
return false;
return true;
}
// Function to return the absolute
// differences of the pairs which
// satisfy the given condition
function findSum( arr, n)
{
// To store the required sum
let sum = 0;
for (let i = 0; i < n - 1; i++) {
for (let j = i + 1; j < n; j++)
// If difference between the indices
// is prime
if (isPrime(j - i)) {
// Update the sum with the absolute
// difference of the pair elements
sum = sum + Math.abs(arr[i] - arr[j]);
}
}
// Return the sum
return sum;
}
// Driver code
let arr = [ 1, 2, 3, 5, 7, 12 ];
let n = arr.length;
document.write(findSum(arr, n));
</script>
Output
45
Time Complexity: O(N3)
Auxiliary Space: O(1)
Approach using Prime Difference and Pre-computation
This solution optimizes the sum of absolute differences calculation by improving the prime checking process. Instead of checking whether each index difference is prime inside the nested loop, we pre-compute prime numbers up to the maximum possible index difference using the Sieve of Eratosthenes. This reduces the time complexity of the prime-checking portion from linear to logarithmic per difference check. We then use these pre-computed prime statuses to quickly verify if the difference between indices is prime before calculating the difference of their corresponding array values.
Follow the steps to solve the problem:
- Pre-compute primes using the Sieve of Eratosthenes, which provides an efficient way to find all prime numbers up to a given limit.
- Use a nested loop to iterate over array pairs and calculate absolute differences only when the index difference is prime.
- Reduce computational overhead by avoiding redundant prime checks during pair comparisons.
Below is the implementation of above approach:
#include <cmath>
#include <iostream>
#include <vector>
// Function to use the Sieve of Eratosthenes to mark prime
// numbers up to a given limit
std::vector<bool> sieveOfEratosthenes(int maxNum)
{
std::vector<bool> isPrime(maxNum + 1, true);
isPrime[0] = isPrime[1]
= false; // 0 and 1 are not primes
for (int p = 2; p * p <= maxNum; p++) {
if (isPrime[p]) {
for (int i = p * p; i <= maxNum; i += p) {
isPrime[i] = false;
}
}
}
return isPrime;
}
// Function to return the absolute differences of the pairs
// which satisfy the given prime condition
int findSum(int arr[], int n)
{
// To store the required sum
int sum = 0;
// Precompute primes up to n-1 using Sieve of
// Eratosthenes
std::vector<bool> prime = sieveOfEratosthenes(n - 1);
// Calculate the sum of absolute differences where index
// differences are prime
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (prime[j - i]) {
sum += abs(arr[i] - arr[j]);
}
}
}
return sum;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3, 5, 7, 12 };
int n = sizeof(arr) / sizeof(arr[0]);
std::cout << findSum(arr, n)
<< std::endl; // Output should be 45
return 0;
}
import java.util.Arrays;
public class Main {
// Function to use the Sieve of Eratosthenes to mark
// prime numbers up to a given limit
static boolean[] sieveOfEratosthenes(int maxNum)
{
boolean[] isPrime = new boolean[maxNum + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1]
= false; // 0 and 1 are not primes
for (int p = 2; p * p <= maxNum; p++) {
if (isPrime[p]) {
for (int i = p * p; i <= maxNum; i += p) {
isPrime[i] = false;
}
}
}
return isPrime;
}
// Function to return the absolute differences of the
// pairs which satisfy the given prime condition
static int findSum(int[] arr)
{
int n = arr.length;
// To store the required sum
int sum = 0;
// Precompute primes up to n-1 using Sieve of
// Eratosthenes
boolean[] prime = sieveOfEratosthenes(n - 1);
// Calculate the sum of absolute differences where
// index differences are prime
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (prime[j - i]) {
sum += Math.abs(arr[i] - arr[j]);
}
}
}
return sum;
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 1, 2, 3, 5, 7, 12 };
System.out.println(
findSum(arr)); // Output should be 45
}
}
import math
def sieve_of_eratosthenes(max_num):
"""
Function to use the Sieve of Eratosthenes to mark prime numbers up to a given limit.
Args:
- max_num (int): The maximum number up to which primes are to be identified.
Returns:
- list[bool]: A boolean list where True indicates that the index is a prime number.
"""
is_prime = [True] * (max_num + 1)
is_prime[0] = is_prime[1] = False # 0 and 1 are not prime numbers.
for p in range(2, int(math.sqrt(max_num)) + 1):
if is_prime[p]:
for i in range(p * p, max_num + 1, p):
is_prime[i] = False
return is_prime
def find_sum(arr):
"""
Function to return the sum of absolute differences of array elements at indices
where the difference between indices is prime.
Args:
- arr (list[int]): The array of integers.
Returns:
- int: The sum of absolute differences where index differences are prime.
"""
n = len(arr)
# Precompute primes up to n-1 using Sieve of Eratosthenes
prime = sieve_of_eratosthenes(n - 1)
sum_diff = 0
# Calculate the sum of absolute differences where index differences are prime
for i in range(n - 1):
for j in range(i + 1, n):
if prime[j - i]:
sum_diff += abs(arr[i] - arr[j])
return sum_diff
# Driver code
if __name__ == "__main__":
arr = [1, 2, 3, 5, 7, 12]
# Calling the function to calculate the sum of prime-indexed differences
result = find_sum(arr)
print(result) # Output should be 45
// Function to use the Sieve of Eratosthenes to mark
// prime numbers up to a given limit
function sieveOfEratosthenes(maxNum) {
const isPrime = new Array(maxNum + 1).fill(true);
isPrime[0] = isPrime[1] = false; // 0 and 1 are not primes
for (let p = 2; p * p <= maxNum; p++) {
if (isPrime[p]) {
for (let i = p * p; i <= maxNum; i += p) {
isPrime[i] = false;
}
}
}
return isPrime;
}
// Function to return the absolute differences of the
// pairs which satisfy the given prime condition
function findSum(arr) {
const n = arr.length;
// To store the required sum
let sum = 0;
// Precompute primes up to n-1 using Sieve of
// Eratosthenes
const prime = sieveOfEratosthenes(n - 1);
// Calculate the sum of absolute differences where
// index differences are prime
for (let i = 0; i < n - 1; i++) {
for (let j = i + 1; j < n; j++) {
if (prime[j - i]) {
sum += Math.abs(arr[i] - arr[j]);
}
}
}
return sum;
}
// Driver code
const arr = [1, 2, 3, 5, 7, 12];
console.log(findSum(arr)); // Output should be 45
Output
45
Time Complexity: O(N^2 + K log log K), where N is the number of elements in the array and K is the maximum index difference (nearly N). The nested loop runs in O(N^2) and the Sieve of Eratosthenes runs in O(KloglogK).
Auxilary Space: O(K), where K is the maximum index difference. This space is used to store the prime status of each index difference up to N−1. This represents a significant improvement over the simpler approach, especially in terms of time complexity during the prime checking phase.