Display differences of all consecutive pairs of numbers in the list

Absolute Difference of all pairwise consecutive elements in an array

Given an array of integers of N elements. The task is to print the absolute difference of all of the pairwise consecutive elements.
Pairwise consecutive pairs of an array of size N are (a[i], a[i+1]) for all i ranging from 0 to N-2
Examples:

Table of Contents Show

Absolute Difference of all pairwise consecutive elements in an array
Count consecutive pairs of same elements
Check for pair in an array with a given sum - Interview Problem

Input: arr[] = {8, 5, 4, 3, 15, 20} Output: 3, 1, 1, 12, 5 Input: arr[] = {5, 10, 15, 20} Output: 5, 5, 5

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach: The solution is to traverse the array and calculate and print the absolute difference of every pair (arr[i], arr[i+1]).
Below is the implementation of the above approach:

C++

// C++ program to print the absolute
// difference of the consecutive elements
#include <iostream>

using namespace std;
// Function to print pairwise absolute
// difference of consecutive elements

void pairwiseDifference(int arr[], int n)
{

int diff;

for (int i = 0; i < n - 1; i++) {

// absolute difference between

// consecutive numbers

diff = abs(arr[i] - arr[i + 1]);

cout << diff << " ";

}
}
// Driver Code

int main()
{

int arr[] = { 4, 10, 15, 5, 6 };

int n = sizeof(arr) / sizeof(arr[0]);

pairwiseDifference(arr, n);

return 0;
}

Java

// Java program to print the absolute 
// difference of the consecutive elements 

class GFG{
// Function to print pairwise absolute 
// difference of consecutive elements 

static void pairwiseDifference(int arr[], int n)
{ 

int diff;

for (int i = 0; i < n - 1; i++) {

// absolute difference between

// consecutive numbers

diff = Math.abs(arr[i] - arr[i + 1]);

System.out.print(diff+" ");

}
} 
// Driver Code 

public static void main(String[] args)
{ 

int arr[] = { 4, 10, 15, 5, 6 };

int n = arr.length;

pairwiseDifference(arr, n);
} 
}
// This code is contributed by mits

Python 3

# Python 3 program to print the absolute
# difference of the consecutive elements
# Function to print pairwise absolute
# difference of consecutive elements

def pairwiseDifference(arr, n):


for i in range(n - 1) :

# absolute difference between

# consecutive numbers

diff = abs(arr[i] - arr[i + 1])

print(diff , end = " ")
# Driver Code

if __name__=="__main__":

arr = [ 4, 10, 15, 5, 6 ]

n = len(arr)

pairwiseDifference(arr, n)
# This code is contributed 
# by ChitraNayal

// C# program to print the absolute 
// difference of the consecutive elements 

using System;

class GFG{
// Function to print pairwise absolute 
// difference of consecutive elements 

static void pairwiseDifference(int []arr, int n)
{ 

int diff;

for (int i = 0; i < n - 1; i++) {

// absolute difference between

// consecutive numbers

diff = Math.Abs(arr[i] - arr[i + 1]);

Console.WriteLine(diff+" ");

}
} 
// Driver Code 

public static void Main(String[] args)
{ 

int []arr = { 4, 10, 15, 5, 6 };

int n = arr.Length;

pairwiseDifference(arr, n);
} 
}

PHP

<?php
// PHP program to print the absolute
// difference of the consecutive elements
// Function to print pairwise absolute
// difference of consecutive elements

function pairwiseDifference($arr, $n)
{

$diff = 0;

for ($i = 0; $i < $n - 1; $i++)

{

// absolute difference between

// consecutive numbers

$diff = abs($arr[$i] - $arr[$i + 1]);

echo $diff." ";

}
}
// Driver Code

$arr = array( 4, 10, 15, 5, 6 );

$n = sizeof($arr);

pairwiseDifference($arr, $n);
// This code is contributed by mits
?>

Javascript

<script>
// javascript program to print the absolute 
// difference of the consecutive elements 
// Function to print pairwise absolute

// difference of consecutive elements

function pairwiseDifference(arr , n) {

var diff;

for (i = 0; i < n - 1; i++) {

// absolute difference between

// consecutive numbers

diff = Math.abs(arr[i] - arr[i + 1]);

document.write(diff + " ");

}

}

// Driver Code

var arr = [ 4, 10, 15, 5, 6 ];

var n = arr.length;

pairwiseDifference(arr, n);
// This code contributed by umadevi9616 
</script>

Output: 6 5 10 1

Time complexity : O(n)

Article Tags :

Arrays

Mathematical

School Programming

Technical Scripter

Technical Scripter 2018

Practice Tags :

Arrays

Mathematical

Read Full Article

Count consecutive pairs of same elements

Given an array arr[], the task is to count the number of pairs formed by consecutive elements in which both of the elements in a pair are same.
Examples:

Input: arr[] = {1, 2, 2, 3, 4, 4, 5, 5, 5, 5}
Output: 5
(1, 2), (4, 5), (6, 7), (7, 8) and (8, 9) are the valid index pairs
where consecutive elements are equal.
Input: arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Output: 0
No two consecutive elements in the given array are equal.

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach: Initialize count = 0 and traverse the array from arr[0] to arr[n – 2]. If the current element is equal to the next element in the array then increment the count. Print the count in the end.
Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <iostream>

using namespace std;
// Function to return the count of consecutive
// elements in the array which are equal

int countCon(int ar[], int n)
{

int cnt = 0;

for (int i = 0; i < n - 1; i++) {

// If consecutive elements are same

if (ar[i] == ar[i + 1])

cnt++;

}

return cnt;
}
// Driver code

int main()
{

int ar[] = { 1, 2, 2, 3, 4, 4, 5, 5, 5, 5 };

int n = sizeof(ar) / sizeof(ar[0]);

cout << countCon(ar, n);

return 0;
}

Java

// Java implementation of the approach 

public class GfG
{

// Function to return the count of consecutive

// elements in the array which are equal

static int countCon(int ar[], int n)

{

int cnt = 0;

for (int i = 0; i < n - 1; i++)

{

// If consecutive elements are same

if (ar[i] == ar[i + 1])

cnt++;

}

return cnt;

}

// Driver Code

public static void main(String []args){

int ar[] = { 1, 2, 2, 3, 4, 4, 5, 5, 5, 5 };

int n = ar.length;

System.out.println(countCon(ar, n));

}
}
// This code is contributed by Rituraj Jain

Python3

# Python3 implementation of the approach
# Function to return the count of consecutive
# elements in the array which are equal

def countCon(ar, n):

cnt = 0

for i in range(n - 1):

# If consecutive elements are same

if (ar[i] == ar[i + 1]):

cnt += 1

return cnt
# Driver code

ar = [1, 2, 2, 3, 4,

4, 5, 5, 5, 5]

n = len(ar)

print(countCon(ar, n))
# This code is contributed by mohit kumar

// C# implementation of the approach 

using System;

class GfG
{

// Function to return the count of consecutive

// elements in the array which are equal

static int countCon(int[] ar, int n)

{

int cnt = 0;

for (int i = 0; i < n - 1; i++)

{

// If consecutive elements are same

if (ar[i] == ar[i + 1])

cnt++;

}

return cnt;

}

// Driver Code

public static void Main()

{

int[] ar = { 1, 2, 2, 3, 4, 4, 5, 5, 5, 5 };

int n = ar.Length;

Console.WriteLine(countCon(ar, n));

}
}
// This code is contributed by Code_Mech.

PHP

<?php
// PHP implementation of the approach
// Function to return the count of consecutive
// elements in the array which are equal

function countCon($ar, $n)
{

$cnt = 0;

for ($i = 0; $i < $n - 1; $i++)

{

// If consecutive elements are same

if ($ar[$i] == $ar[$i + 1])

$cnt++;

}

return $cnt;
}
// Driver code

$ar = array(1, 2, 2, 3, 4, 4, 5, 5, 5, 5);

$n = sizeof($ar);

echo countCon($ar, $n);
// This code is contributed
// by Akanksha Rai
?>

Javascript

<script>
// Javascript implementation of the approach 

// Function to return the count of consecutive

// elements in the array which are equal

function countCon(ar,n)

{

let cnt = 0;

for (let i = 0; i < n - 1; i++)

{

// If consecutive elements are same

if (ar[i] == ar[i + 1])

cnt++;

}

return cnt;

}

// Driver Code

let ar = [1, 2, 2, 3, 4, 4, 5, 5, 5, 5 ];

let n = ar.length;

document.write(countCon(ar, n));
// This code is contributed by unknown2108
</script>

Output: 5

Article Tags :

Arrays

Mathematical

Constructive Algorithms

Practice Tags :

Arrays

Mathematical

Read Full Article

Check for pair in an array with a given sum - Interview Problem

Difficulty Level : Medium

Asked in : Google, Facebook, Amazon

Understanding the problem

Problem Description: Given an array of n integers and given a number K, determines whether there is a pair of elements in the array that sums to exactly K.

For example :

Input : A[] = [-5, 1, -40, 20, 6, 8, 7 ], K=15

Output: true ( 7, 8 and -5, 20 are the pairs with sum 15)

Input : A[] = [-5, 4, -2, 16, 8, 9], K=15

Output: false (There is no pair of elements whose sum is equal to 15)

Possible follow-up questions to ask the interviewer :

Do we know something about the range of the numbers in the array? Ans: No, they can be arbitrary integers.
Are the array elements necessarily positive? Ans: No, they can be positive, negative, or zero.
Do we know anything about the value of K relative to the numbers in the array? Ans: No, it can be arbitrary.
Can we consider pairs of an element and itself? Ans: No, the pair should consist of two different array elements.
Can the array contain duplicates? Ans: Sure, that's a possibility.

Designing efficient solutions

We are discussing four ways to solve this problem :

Brute force Approach: Using two loops
Sorting and binary search
Sorting and two Pointer approach
Using a Hash Table

1. Brute Force Approach: Using two loops

Use two loops and check A[i] + A[j] == K for each pair (i, j) in A[]. If there exists a pair with sum equals to K then return true. By end of both loops, If you didn’t find such a pair then return false.

Pseudo Code

int find_sumPair (A[], n, K) { for( i = 0 to n-1 ) { for(j = i+1 to n-1) { if(A[i]+A[j] == K) return 1 } } return -1 }

Complexity Analysis

The total no. of comparison in worst case = Total no. of possible pairs = nC2 = n(n-1)/2 = O(n²)

Time Complexity = O(n²) and Space Complexity = O(1). Can we improve the time complexity? Let's try to think about it.

2. Sorting and Binary Search

The idea of binary search works perfectly in the case of the sorted array. We can sort the A[] and for each value A[i], search whether there is another value K-A[i] present in the array or not. Binary search performs searching in O(logn) which could help us to improve the time complexity.

Solution Steps

Sort the array A[] in increasing order
For each element A[i], use binary search to look for K-A[i].
If there exists a value K-A[i] in the array A, then return true.
If you didn’t find such a pair in the whole array , then return false.

Pseudo Code

int find_sumPair (A[], n, K) { Sort ( A, n) for( i = 0 to n-1 ) { x = binarySearch ( A, 0, n-1, K-A[i] ) if ( x ) return 1 } return -1 }

Complexity Analysis

Suppose we are using heap sort/merge sort and iterative binary search for the implementation.

Time Complexity = Time complexity of sorting + n. Time complexity of Binary Search = O(nlogn) + n. O(logn) = O(nlogn)

Space Complexity = Space Complexity of sorting + Space complexity of the binary search (Iterative Implementation)

If merge sort ,Space Complexity = O(n) + O(1) = O(n)

If Heap Sort, Space Complexity = O(1) + O(1) = O(1)

Critical Ideas to think!

What would be the time and space complexity if we use quicksort? Compare different sorting algorithms
What would be the space complexity of the recursive binary search?
Why are we searching K - A[i] for each element in array A[]?
Prepare a list of problems where you can apply the idea of sorting and binary search.

3. Sorting and two Pointer approach

Sort the array A[] then walk two pointers inward from the ends of the array, at each point looking at their sum. If it is exactly k, then we are done. If it exceeds k, then any sum using the larger element is too large, so we walk that pointer inwards. If it is less than k, then any sum using the lower element is too small, so we walk that pointer inwards.

Solution Steps

Sort the array A[] in increasing order
Initialize two index variables in the sorted array A[].

left pointer: i = 0
right pointer : j = n-1

3) Run a loop while i< j.

If (A[i] + A[j] == K) then return true
if( A[i] + A[j] < K) then increment i by 1
if( A[i] + A[j] > K) then decrement j by 1

4) If didn’t find such a pair in the whole array - return false.

Solution Visualization

Pseudo Code

int find_sumPair( A[], n, K) { Sort(A, n) i = 0 j = n -1 while (i < j) { if(A[i] + A[j] == K) return 1 else if(A[i] + A[j] < K) i = i+1 else j = j-1 } return -1 }

Complexity Analysis

Suppose we are using Heap Sort or merge sort.

Time Complexity = Time complexity of sorting + Time complexity of two pointer approach (while loop) = O (n log n) + O(n) = O (n log n)

If merge sort, Space Complexity = O(n)

If Heap Sort, Space Complexity = O(1)

Critical Ideas to think!

is this algorithm works fine if elements are repeated?
The time complexity of while loop is O(n) in the worst-case - why?
Why the idea of the two pointer approach works perfectly for a sorted array?
Prepare a list of problems where you can apply the idea of two pointer approach for the solution.

4. Using a Hash Table

Idea is to use the Hash Table to improve the time complexity because it performs searching and insertion efficiently in O(1) average.

Solution Steps

Take a Hash Table H of size O(n)
Run a loop and scan over the array A[] for each A[i]. Check if K-A[i] is present in the hash table or not.

If yes, we have found the pair and return true.
If no, then insert A[i] into the Hash table

3. If you didn’t find such a pair by end of the loop then return false.

Pseudo Code

bool checkPair(int A[], int n, int K) { Take Hash Table H of size O(n) for (i = 0 to n-1) { int x = K - A[i] if (H.search(x) is true) return 1 H.insert(A[i]) } return -1 }

Complexity Analysis

In worst case scenario, we scan the whole array and didn't find any such pair. Time Complexity = Time complexity of inserting n elements in hash table + Time complexity of searching (K-A[i]) n times in hash table = n. O(1) + n . O(1) = O(n)

Space Complexity = Extra space of Hash Table = O(n)

Critical Ideas to think!

is this algorithm works fine if elements are repeated?
What would be the time and space complexity if we use a binary search tree in place of a hash table? Compare hash table and binary search tree
This is also a good example of problem-solving via data structure. Prepare a list of problems where we use data structures (hash table, BST, priority queue, stack, queue, etc) for the efficient solution.
Is there any other way to solve this problem? Think