Skip to main content

Find pair with given sum in sorted and rotated array

Here given code implementation process.

// C Program 
// Find pair with given sum in sorted and rotated array
#include <stdio.h>

//Function which is display array elements
void display(int arr[], int size)
{
	for (int i = 0; i < size; ++i)
	{
		printf("  %d", arr[i]);
	}
	printf("\n");
}
//Finding the sum of pair in given sorted rotated array
void find_pair_sum(int arr[], int size, int sum)
{
	if (size < 2)
	{
		return;
	}
	//Display array element
	printf("\n Array  :");
	display(arr, size);
	//Variable which is indicates given sum pair are exist or not
	int status = 0;
	//variable which is used to store the result
	int lower = 0;
	int higher = 0;
	//Find largest element in sorted or rotated sorted array
	while (higher + 1 < size && arr[higher] <= arr[higher + 1])
	{
		higher++;
	}
	//Get the location of smallest element
	lower = (higher + 1) % size;
	while (status == 0 && lower != higher)
	{
		if (arr[lower] + arr[higher] == sum)
		{
			//When get pair of given sum
			status = 1;
		}
		else if (arr[lower] + arr[higher] > sum)
		{
			//reduce higher element location
			higher = (higher - 1) % size;
		}
		else
		{
			lower = (size + lower + 1) % size;
		}
	}
	if (status == 1)
	{
		//When solutions are exists
		printf(" Sum of pair %d is : [(%d) + (%d)]\n", sum, arr[lower], arr[higher]);
	}
	else
	{
		//When solutions are not exists
		printf(" Sum of %d are not exists \n", sum);
	}
}
int main()
{
	//Define array of integer elements
	int arr1[] = {
		15 , 16 , 17 , 30 , 1 , 9 , 10 , 14
	};
	//Get the size of array
	int size = sizeof(arr1) / sizeof(arr1[0]);
	int sum = 25;
	find_pair_sum(arr1, size, sum);
	int arr2[] = {
		7 , 9 , 10 , 17 , -2 , 1 , 2 , 2 , 5
	};
	//Get the size of array
	size = sizeof(arr2) / sizeof(arr2[0]);
	sum = 43;
	find_pair_sum(arr2, size, sum);
	sum = 14;
	find_pair_sum(arr2, size, sum);
	return 0;
}

Output

 Array  :  15  16  17  30  1  9  10  14
 Sum of pair 25 is : [(9) + (16)]

 Array  :  7  9  10  17  -2  1  2  2  5
 Sum of 43 are not exists

 Array  :  7  9  10  17  -2  1  2  2  5
 Sum of pair 14 is : [(5) + (9)]
// Java Program
// Find pair with given sum in sorted and rotated array
class MyArray
{
	//Function which is display array elements
	public void display(int[] arr, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			System.out.print(" " + arr[i]);
		}
		System.out.print("\n");
	}
	//Finding the sum of pair in given sorted rotated array
	public void find_pair_sum(int[] arr, int size, int sum)
	{
		if (size < 2)
		{
			return;
		}
		System.out.print("\n Array :");
		display(arr, size);
		//Variable which is indicates given sum pair are exist or not
		int status = 0;
		//variable which is used to store the result
		int lower = 0;
		int higher = 0;
		//Find largest element in sorted or rotated sorted array
		while (higher + 1 < size && arr[higher] <= arr[higher + 1])
		{
			higher++;
		}
		//Get the location of smallest element
		lower = (higher + 1) % size;
		while (status == 0 && lower != higher)
		{
			if (arr[lower] + arr[higher] == sum)
			{
				//When get pair of given sum
				status = 1;
			}
			else if (arr[lower] + arr[higher] > sum)
			{
				//reduce higher element location
				higher = (higher - 1) % size;
			}
			else
			{
				lower = (size + lower + 1) % size;
			}
		}
		if (status == 1)
		{
			System.out.print(" Sum of pair " + sum + " is : [(" + arr[lower] + ") + (" + arr[higher] + ")]\n");
		}
		else
		{
			System.out.print(" Sum of " + sum + " are not exists \n");
		}
	}
	public static void main(String[] args)
	{
		MyArray obj = new MyArray();
		//Define array of integer elements
		int[] arr1 = {
			15,
			16,
			17,
			30,
			1,
			9,
			10,
			14
		};
		//Get the size of array
		int size = arr1.length;
		int sum = 25;
		obj.find_pair_sum(arr1, size, sum);
		int[] arr2 = {
			7,
			9,
			10,
			17,
			-2,
			1,
			2,
			2,
			5
		};
		//Get the size of array
		size = arr2.length;
		sum = 43;
		obj.find_pair_sum(arr2, size, sum);
		sum = 14;
		obj.find_pair_sum(arr2, size, sum);
	}
}

Output

 Array : 15 16 17 30 1 9 10 14
 Sum of pair 25 is : [(9) + (16)]

 Array : 7 9 10 17 -2 1 2 2 5
 Sum of 43 are not exists

 Array : 7 9 10 17 -2 1 2 2 5
 Sum of pair 14 is : [(5) + (9)]
//Include header file
#include <iostream>

using namespace std;
// C++ Program
// Find pair with given sum in sorted and rotated array
class MyArray
{
	public:
		//Function which is display array elements
		void display(int arr[], int size)
		{
			for (int i = 0; i < size; ++i)
			{
				cout << " " << arr[i];
			}
			cout << "\n";
		}
	//Finding the sum of pair in given sorted rotated array
	void find_pair_sum(int arr[], int size, int sum)
	{
		if (size < 2)
		{
			return;
		}
		cout << "\n Array :";
		this->display(arr, size);
		//Variable which is indicates given sum pair are exist or not
		int status = 0;
		//variable which is used to store the result
		int lower = 0;
		int higher = 0;
		//Find largest element in sorted or rotated sorted array
		while (higher + 1 < size && arr[higher] <= arr[higher + 1])
		{
			higher++;
		}
		//Get the location of smallest element
		lower = (higher + 1) % size;
		while (status == 0 && lower != higher)
		{
			if (arr[lower] + arr[higher] == sum)
			{
				//When get pair of given sum
				status = 1;
			}
			else if (arr[lower] + arr[higher] > sum)
			{
				//reduce higher element location
				higher = (higher - 1) % size;
			}
			else
			{
				lower = (size + lower + 1) % size;
			}
		}
		if (status == 1)
		{
			cout << " Sum of pair " << sum << " is : [(" << arr[lower] << ") + (" << arr[higher] << ")]\n";
		}
		else
		{
			cout << " Sum of " << sum << " are not exists \n";
		}
	}
};
int main()
{
	MyArray obj = MyArray();
	int arr1[] = {
		15 , 16 , 17 , 30 , 1 , 9 , 10 , 14
	};
	//Get the size of array
	int size = sizeof(arr1) / sizeof(arr1[0]);
	int sum = 25;
	obj.find_pair_sum(arr1, size, sum);
	int arr2[] = {
		7 , 9 , 10 , 17 , -2 , 1 , 2 , 2 , 5
	};
	//Get the size of array
	size = sizeof(arr2) / sizeof(arr2[0]);
	sum = 43;
	obj.find_pair_sum(arr2, size, sum);
	sum = 14;
	obj.find_pair_sum(arr2, size, sum);
	return 0;
}

Output

 Array : 15 16 17 30 1 9 10 14
 Sum of pair 25 is : [(9) + (16)]

 Array : 7 9 10 17 -2 1 2 2 5
 Sum of 43 are not exists

 Array : 7 9 10 17 -2 1 2 2 5
 Sum of pair 14 is : [(5) + (9)]
//Include namespace system
using System;
// C# Program
// Find pair with given sum in sorted and rotated array
class MyArray
{
	//Function which is display array elements
	public void display(int[] arr, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			Console.Write(" " + arr[i]);
		}
		Console.Write("\n");
	}
	//Finding the sum of pair in given sorted rotated array
	public void find_pair_sum(int[] arr, int size, int sum)
	{
		if (size < 2)
		{
			return;
		}
		Console.Write("\n Array :");
		display(arr, size);
		//Variable which is indicates given sum pair are exist or not
		int status = 0;
		//variable which is used to store the result
		int lower = 0;
		int higher = 0;
		//Find largest element in sorted or rotated sorted array
		while (higher + 1 < size && arr[higher] <= arr[higher + 1])
		{
			higher++;
		}
		//Get the location of smallest element
		lower = (higher + 1) % size;
		while (status == 0 && lower != higher)
		{
			if (arr[lower] + arr[higher] == sum)
			{
				//When get pair of given sum
				status = 1;
			}
			else if (arr[lower] + arr[higher] > sum)
			{
				//reduce higher element location
				higher = (higher - 1) % size;
			}
			else
			{
				lower = (size + lower + 1) % size;
			}
		}
		if (status == 1)
		{
			Console.Write(" Sum of pair " + sum + " is : [(" + arr[lower] + ") + (" + arr[higher] + ")]\n");
		}
		else
		{
			Console.Write(" Sum of " + sum + " are not exists \n");
		}
	}
	public static void Main(String[] args)
	{
		MyArray obj = new MyArray();
		int[] arr1 = {
			15 , 16 , 17 , 30 , 1 , 9 , 10 , 14
		};
		//Get the size of array
		int size = arr1.Length;
		int sum = 25;
		obj.find_pair_sum(arr1, size, sum);
		int[] arr2 = {
			7 , 9 , 10 , 17 , -2 , 1 , 2 , 2 , 5
		};
		//Get the size of array
		size = arr2.Length;
		sum = 43;
		obj.find_pair_sum(arr2, size, sum);
		sum = 14;
		obj.find_pair_sum(arr2, size, sum);
	}
}

Output

 Array : 15 16 17 30 1 9 10 14
 Sum of pair 25 is : [(9) + (16)]

 Array : 7 9 10 17 -2 1 2 2 5
 Sum of 43 are not exists

 Array : 7 9 10 17 -2 1 2 2 5
 Sum of pair 14 is : [(5) + (9)]
<?php
// Php Program
// Find pair with given sum in sorted and rotated array
class MyArray
{
	//Function which is display array elements
	public	function display( $arr, $size)
	{
		for ($i = 0; $i < $size; ++$i)
		{
			echo " ". $arr[$i];
		}
		echo "\n";
	}
	//Finding the sum of pair in given sorted rotated array
	public	function find_pair_sum( $arr, $size, $sum)
	{
		if ($size < 2)
		{
			return;
		}
		echo "\n Array :";
		$this->display($arr, $size);
		//Variable which is indicates given sum pair are exist or not
		$status = 0;
		//variable which is used to store the result
		$lower = 0;
		$higher = 0;
		//Find largest element in sorted or rotated sorted array
		while ($higher + 1 < $size && $arr[$higher] <= $arr[$higher + 1])
		{
			$higher++;
		}
		//Get the location of smallest element
		$lower = ($higher + 1) % $size;
		while ($status == 0 && $lower != $higher)
		{
			if ($arr[$lower] + $arr[$higher] == $sum)
			{
				//When get pair of given sum
				$status = 1;
			}
			else if ($arr[$lower] + $arr[$higher] > $sum)
			{
				//reduce higher element location
				$higher = ($higher - 1) % $size;
			}
			else
			{
				$lower = ($size + $lower + 1) % $size;
			}
		}
		if ($status == 1)
		{
			echo " Sum of pair ". $sum ." is : [(". $arr[$lower] .") + (". $arr[$higher] .")]\n";
		}
		else
		{
			echo " Sum of ". $sum ." are not exists \n";
		}
	}
}

function main()
{
	$obj = new MyArray();
	//Define array of integer elements
	$arr1 = array(15, 16, 17, 30, 1, 9, 10, 14);
	//Get the size of array
	$size = count($arr1);
	$sum = 25;
	$obj->find_pair_sum($arr1, $size, $sum);
	$arr2 = array(7, 9, 10, 17, -2, 1, 2, 2, 5);
	//Get the size of array
	$size = count($arr2);
	$sum = 43;
	$obj->find_pair_sum($arr2, $size, $sum);
	$sum = 14;
	$obj->find_pair_sum($arr2, $size, $sum);
}
main();

Output

 Array : 15 16 17 30 1 9 10 14
 Sum of pair 25 is : [(9) + (16)]

 Array : 7 9 10 17 -2 1 2 2 5
 Sum of 43 are not exists

 Array : 7 9 10 17 -2 1 2 2 5
 Sum of pair 14 is : [(5) + (9)]
// Node Js Program
// Find pair with given sum in sorted and rotated array
class MyArray
{
	//Function which is display array elements
	display(arr, size)
	{
		for (var i = 0; i < size; ++i)
		{
			process.stdout.write(" " + arr[i]);
		}
		process.stdout.write("\n");
	}
	//Finding the sum of pair in given sorted rotated array
	find_pair_sum(arr, size, sum)
	{
		if (size < 2)
		{
			return;
		}
		process.stdout.write("\n Array :");
		this.display(arr, size);
		//Variable which is indicates given sum pair are exist or not
		var status = 0;
		//variable which is used to store the result
		var lower = 0;
		var higher = 0;
		//Find largest element in sorted or rotated sorted array
		while (higher + 1 < size && arr[higher] <= arr[higher + 1])
		{
			higher++;
		}
		//Get the location of smallest element
		lower = (higher + 1) % size;
		while (status == 0 && lower != higher)
		{
			if (arr[lower] + arr[higher] == sum)
			{
				//When get pair of given sum
				status = 1;
			}
			else if (arr[lower] + arr[higher] > sum)
			{
				//reduce higher element location
				higher = (higher - 1) % size;
			}
			else
			{
				lower = (size + lower + 1) % size;
			}
		}
		if (status == 1)
		{
			process.stdout.write(" Sum of pair " + sum + " is : [(" + arr[lower] + ") + (" + arr[higher] + ")]\n");
		}
		else
		{
			process.stdout.write(" Sum of " + sum + " are not exists \n");
		}
	}
}

function main()
{
	var obj = new MyArray();
	//Define array of integer elements
	var arr1 = [15, 16, 17, 30, 1, 9, 10, 14];
	//Get the size of array
	var size = arr1.length;
	var sum = 25;
	obj.find_pair_sum(arr1, size, sum);
	var arr2 = [7, 9, 10, 17, -2, 1, 2, 2, 5];
	//Get the size of array
	size = arr2.length;
	sum = 43;
	obj.find_pair_sum(arr2, size, sum);
	sum = 14;
	obj.find_pair_sum(arr2, size, sum);
}
main();

Output

 Array : 15 16 17 30 1 9 10 14
 Sum of pair 25 is : [(9) + (16)]

 Array : 7 9 10 17 -2 1 2 2 5
 Sum of 43 are not exists

 Array : 7 9 10 17 -2 1 2 2 5
 Sum of pair 14 is : [(5) + (9)]
#  Python 3 Program
#  Find pair with given sum in sorted and rotated array
class MyArray :
	# Function which is display array elements
	def display(self, arr, size) :
		i = 0
		while (i < size) :
			print(" ", arr[i], end = "")
			i += 1
		
		print("\n", end = "")
	
	# Finding the sum of pair in given sorted rotated array
	def find_pair_sum(self, arr, size, sum) :
		if (size < 2) :
			return
		
		print("\n Array :", end = "")
		self.display(arr, size)
		# Variable which is indicates given sum pair are exist or not
		status = 0
		# variable which is used to store the result
		lower = 0
		higher = 0
		# Find largest element in sorted or rotated sorted array
		while (higher + 1 < size and arr[higher] <= arr[higher + 1]) :
			higher += 1
		
		# Get the location of smallest element
		lower = (higher + 1) % size
		while (status == 0 and lower != higher) :
			if (arr[lower] + arr[higher] == sum) :
				# When get pair of given sum
				status = 1
			
			elif(arr[lower] + arr[higher] > sum) :
				# reduce higher element location
				higher = (higher - 1) % size
			else :
				lower = (size + lower + 1) % size
			
		
		if (status == 1) :
			print(" Sum of pair ", sum ," is : [(", arr[lower] ,") + (", arr[higher] ,")]\n", end = "")
		else :
			print(" Sum of ", sum ," are not exists \n", end = "")
		
	

def main() :
	obj = MyArray()
	# Define array of integer elements
	arr1 = [15, 16, 17, 30, 1, 9, 10, 14]
	# Get the size of array
	size = len(arr1)
	sum = 25
	obj.find_pair_sum(arr1, size, sum)
	arr2 = [7, 9, 10, 17, -2, 1, 2, 2, 5]
	# Get the size of array
	size = len(arr2)
	sum = 43
	obj.find_pair_sum(arr2, size, sum)
	sum = 14
	obj.find_pair_sum(arr2, size, sum)

if __name__ == "__main__": main()

Output

 Array :  15  16  17  30  1  9  10  14
 Sum of pair  25  is : [( 9 ) + ( 16 )]

 Array :  7  9  10  17  -2  1  2  2  5
 Sum of  43  are not exists

 Array :  7  9  10  17  -2  1  2  2  5
 Sum of pair  14  is : [( 5 ) + ( 9 )]
#  Ruby Program
#  Find pair with given sum in sorted and rotated array
class MyArray

	# Function which is display array elements
	def display(arr, size)
	
		i = 0
		while (i < size)
		
			print(" ", arr[i])
			i += 1
		end
		print("\n")
	end
	# Finding the sum of pair in given sorted rotated array
	def find_pair_sum(arr, size, sum)
	
		if (size < 2)
		
			return
		end
		print("\n Array :")
		self.display(arr, size)
		# Variable which is indicates given sum pair are exist or not
		status = 0
		# variable which is used to store the result
		lower = 0
		higher = 0
		# Find largest element in sorted or rotated sorted array
		while (higher + 1 < size && arr[higher] <= arr[higher + 1])
		
			higher += 1
		end
		# Get the location of smallest element
		lower = (higher + 1) % size
		while (status == 0 && lower != higher)
		
			if (arr[lower] + arr[higher] == sum)
			
				# When get pair of given sum
				status = 1
			elsif(arr[lower] + arr[higher] > sum)
			
				# reduce higher element location
				higher = (higher - 1) % size
			else
			
				lower = (size + lower + 1) % size
			end
		end
		if (status == 1)
		
			print(" Sum of pair ", sum ," is : [(", arr[lower] ,") + (", arr[higher] ,")]\n")
		else
		
			print(" Sum of ", sum ," are not exists \n")
		end
	end
end
def main()

	obj = MyArray.new()
	# Define array of integer elements
	arr1 = [15, 16, 17, 30, 1, 9, 10, 14]
	# Get the size of array
	size = arr1.length
	sum = 25
	obj.find_pair_sum(arr1, size, sum)
	arr2 = [7, 9, 10, 17, -2, 1, 2, 2, 5]
	# Get the size of array
	size = arr2.length
	sum = 43
	obj.find_pair_sum(arr2, size, sum)
	sum = 14
	obj.find_pair_sum(arr2, size, sum)
end
main()

Output

 Array : 15 16 17 30 1 9 10 14
 Sum of pair 25 is : [(9) + (16)]

 Array : 7 9 10 17 -2 1 2 2 5
 Sum of 43 are not exists 

 Array : 7 9 10 17 -2 1 2 2 5
 Sum of pair 14 is : [(5) + (9)]
// Scala Program
// Find pair with given sum in sorted and rotated array
class MyArray
{
	//Function which is display array elements
	def display(arr: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		while (i < size)
		{
			print(" " + arr(i));
			i += 1;
		}
		print("\n");
	}
	//Finding the sum of pair in given sorted rotated array
	def find_pair_sum(arr: Array[Int], size: Int, sum: Int): Unit = {
		if (size < 2)
		{
			return;
		}
		print("\n Array :");
		display(arr, size);
		//Variable which is indicates given sum pair are exist or not
		var status: Int = 0;
		//variable which is used to store the result
		var lower: Int = 0;
		var higher: Int = 0;
		//Find largest element in sorted or rotated sorted array
		while (higher + 1 < size && arr(higher) <= arr(higher + 1))
		{
			higher += 1;
		}
		//Get the location of smallest element
		lower = (higher + 1) % size;
		while (status == 0 && lower != higher)
		{
			if (arr(lower) + arr(higher) == sum)
			{
				//When get pair of given sum
				status = 1;
			}
			else if (arr(lower) + arr(higher) > sum)
			{
				//reduce higher element location
				higher = (higher - 1) % size;
			}
			else
			{
				lower = (size + lower + 1) % size;
			}
		}
		if (status == 1)
		{
			print(" Sum of pair " + sum + " is : [(" + arr(lower) + ") + (" + arr(higher) + ")]\n");
		}
		else
		{
			print(" Sum of " + sum + " are not exists \n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MyArray = new MyArray();
		//Define array of integer elements
		var arr1: Array[Int] = Array(15, 16, 17, 30, 1, 9, 10, 14);
		//Get the size of array
		var size: Int = arr1.length;
		var sum: Int = 25;
		obj.find_pair_sum(arr1, size, sum);
		var arr2: Array[Int] = Array(7, 9, 10, 17, -2, 1, 2, 2, 5);
		//Get the size of array
		size = arr2.length;
		sum = 43;
		obj.find_pair_sum(arr2, size, sum);
		sum = 14;
		obj.find_pair_sum(arr2, size, sum);
	}
}

Output

 Array : 15 16 17 30 1 9 10 14
 Sum of pair 25 is : [(9) + (16)]

 Array : 7 9 10 17 -2 1 2 2 5
 Sum of 43 are not exists

 Array : 7 9 10 17 -2 1 2 2 5
 Sum of pair 14 is : [(5) + (9)]
// Swift Program
// Find pair with given sum in sorted and rotated array
class MyArray
{
	//Function which is display array elements
	func display(_ arr: [Int], _ size: Int)
	{
		var i: Int = 0;
		while (i < size)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
		print("\n", terminator: "");
	}
	//Finding the sum of pair in given sorted rotated array
	func find_pair_sum(_ arr: [Int], _ size: Int, _ sum: Int)
	{
		if (size < 2)
		{
			return;
		}
		print("\n Array :", terminator: "");
		self.display(arr, size);
		//Variable which is indicates given sum pair are exist or not
		var status: Int = 0;
		//variable which is used to store the result
		var lower: Int = 0;
		var higher: Int = 0;
		//Find largest element in sorted or rotated sorted array
		while (higher + 1 < size && arr[higher] <= arr[higher + 1])
		{
			higher += 1;
		}
		//Get the location of smallest element
		lower = (higher + 1) % size;
		while (status == 0 && lower != higher)
		{
			if (arr[lower] + arr[higher] == sum)
			{
				//When get pair of given sum
				status = 1;
			}
			else if (arr[lower] + arr[higher] > sum)
			{
				//reduce higher element location
				higher = (higher - 1) % size;
			}
			else
			{
				lower = (size + lower + 1) % size;
			}
		}
		if (status == 1)
		{
			print(" Sum of pair ", sum ," is : [(", arr[lower] ,") + (", arr[higher] ,")]\n", terminator: "");
		}
		else
		{
			print(" Sum of ", sum ," are not exists \n", terminator: "");
		}
	}
}
func main()
{
	let obj: MyArray = MyArray();
	//Define array of integer elements
	let arr1: [Int] = [15, 16, 17, 30, 1, 9, 10, 14];
	//Get the size of array
	var size: Int = arr1.count;
	var sum: Int = 25;
	obj.find_pair_sum(arr1, size, sum);
	let arr2: [Int] = [7, 9, 10, 17, -2, 1, 2, 2, 5];
	//Get the size of array
	size = arr2.count;
	sum = 43;
	obj.find_pair_sum(arr2, size, sum);
	sum = 14;
	obj.find_pair_sum(arr2, size, sum);
}
main();

Output

 Array :  15  16  17  30  1  9  10  14
 Sum of pair  25  is : [( 9 ) + ( 16 )]

 Array :  7  9  10  17  -2  1  2  2  5
 Sum of  43  are not exists

 Array :  7  9  10  17  -2  1  2  2  5
 Sum of pair  14  is : [( 5 ) + ( 9 )]




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment