Count pairs in a sorted array whose product is less than k

The problem at hand involves counting the pairs of elements in a sorted array whose product is less than a given value k. The task requires analyzing a sorted array and identifying pairs of elements whose multiplication results in a value less than k.

For example, given a sorted array arr = [-1, 0, 2, 3, 4, 9] and k being 7, we need to count the pairs of elements whose product is less than 7.

Problem Statement

The problem requires counting the pairs of elements in a sorted array whose product is less than a given value k.

Explanation with Example

Let's consider the example provided: arr = [-1, 0, 2, 3, 4, 9] and k being 7.

We need to count the pairs of elements whose product is less than 7:

• (-1 * 0) = 0
• (-1 * 2) = -2
• (-1 * 3) = -3
• (-1 * 4) = -4
• (-1 * 9) = -9
• (0 * 2) = 0
• (0 * 3) = 0
• (0 * 4) = 0
• (0 * 9) = 0
• (2 * 3) = 6

The total count of such pairs is 10.

Idea to Solve the Problem

To solve this problem, we can follow these steps:

1. Initialize a count variable to keep track of the number of pairs.
2. Set two pointers, start and last, initially pointing to the first and last elements of the array.
3. While start is less than last, check the product of the elements pointed to by start and last.
4. If the product is less than k, increment the count variable.
5. If both elements are of different signs, loop through the array elements between start and last and check their products with start. Increment the count for each valid pair.
6. Move either the start or last pointer based on the comparison with k.
7. Repeat the above steps until start is less than last.

Pseudocode

Function productLessThanK(arr, n, k):
    count = 0
    start = 0
    last = n - 1
    while start < last:
        if (arr[start] * arr[last]) < k:
            count += (last - start)
            if arr[start] < 0 and arr[last] >= 0:
                i = start + 1
                while i < last and arr[i] <= 0:
                    if (arr[start] * arr[i]) < k:
                        count += 1
                    i += 1
                count += last - i
            start += 1
        else:
            last -= 1
    print "K:", k
    print "Result:", count

Algorithm Explanation

1. The productLessThanK function iterates through the array using the start and last pointers while maintaining the sorted order.
2. When the product of the elements at start and last is less than k, the function increments the count and moves either the start or last pointer accordingly.
3. If both elements are of different signs, the function loops through the array elements between start and last and checks their products with start. It increments the count for each valid pair.
4. The count of valid pairs is displayed at the end.

Code Solution

• Java
• C++
• C#
• Go
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin

// Java program for
// Count pairs in a sorted array whose product is less than k
public class ProductPair
{
	// Display array elements
	public void printArray(int[] arr, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			System.out.print(" " + arr[i]);
		}
	}
	public void productLessThanK(int[] arr, int n, int k)
	{
		int count = 0;
		int start = 0;
		int last = n - 1;
		while (start < last)
		{
			if ((arr[start] *arr[last]) < k)
			{
				// Given array is sorted. 
				// And here start and last element product is less than k.
				if (arr[start] < 0 && arr[last] >= 0)
				{
					// When product is combination of two different sign.
					// So we need to checking individual element
					// Current Boundary pair
					count += 1;
					int i = start + 1;
					while (i < last && arr[i] <= 0)
					{
						if (arr[start] *arr[i] < k)
						{
							count += 1;
						}
						i++;
					}
					count += last - i;
				}
				else
				{
					// (last - start) provide number of elements.
					count += (last - start);
				}
				start++;
			}
			else
			{
				last--;
			}
		}
		System.out.print("\n K : " + k);
		// Display calculated result
		System.out.print("\n Result : " + count);
	}
	public static void main(String[] args)
	{
		ProductPair task = new ProductPair();
		int[] arr = {
			-1 , 0 , 2 , 3 , 4 , 9
		};
		int n = arr.length;
		// Display given array
		task.printArray(arr, n);
		// Test A
		int k = 7;
		/*
		    arr = [ -1, 0, 2, 3 , 4, 9  ]

		    k = 7 
		    ----------------------
		    (-1☓0) = 0
		    (-1☓2) = -2
		    (-1☓3) = -3
		    (-1☓4) = -4
		    (-1☓9) = -9
		    (0☓2) = 0
		    (0☓3) = 0
		    (0☓4) = 0
		    (0☓9) = 0
		    (2☓3) = 6
		    ----------------------

		   Resultant pair : 10
		*/
		task.productLessThanK(arr, n, k);
		// Test B
		k = 0;
		/*
		    arr = [ -1, 0, 2, 3 , 4, 9 ]

		    product k = 0   

		    (-1 ☓ 2) = -2
		    (-1 ☓ 3) = -3
		    (-1 ☓ 4) = -4
		    (-1 ☓ 9) = -9

		    -------------------------
		    Resultant pair : 4
		*/
		task.productLessThanK(arr, n, k);
	}
}

 -1 0 2 3 4 9
 K : 7
 Result : 10
 K : 0
 Result : 4

// Include header file
#include <iostream>

using namespace std;
// C++ program for
// Count pairs in a sorted array whose product is less than k
class ProductPair
{
	public:
		// Display array elements
		void printArray(int arr[], int n)
		{
			for (int i = 0; i < n; ++i)
			{
				cout << " " << arr[i];
			}
		}
	void productLessThanK(int arr[], int n, int k)
	{
		int count = 0;
		int start = 0;
		int last = n - 1;
		while (start < last)
		{
			if ((arr[start] *arr[last]) < k)
			{
				// Given array is sorted.
				// And here start and last element product is less than k.
				if (arr[start] < 0 && arr[last] >= 0)
				{
					// When product is combination of two different sign.
					// So we need to checking individual element
					// Current Boundary pair
					count += 1;
					int i = start + 1;
					while (i < last && arr[i] <= 0)
					{
						if (arr[start] *arr[i] < k)
						{
							count += 1;
						}
						i++;
					}
					count += last - i;
				}
				else
				{
					// (last - start) provide number of elements.
					count += (last - start);
				}
				start++;
			}
			else
			{
				last--;
			}
		}
		cout << "\n K : " << k;
		// Display calculated result
		cout << "\n Result : " << count;
	}
};
int main()
{
	ProductPair *task = new ProductPair();
	int arr[] = {
		-1 , 0 , 2 , 3 , 4 , 9
	};
	int n = sizeof(arr) / sizeof(arr[0]);
	// Display given array
	task->printArray(arr, n);
	// Test A
	int k = 7;
	/*
	    arr = [ -1, 0, 2, 3 , 4, 9  ]
	    k = 7 
	    ----------------------
	    (-1☓0) = 0
	    (-1☓2) = -2
	    (-1☓3) = -3
	    (-1☓4) = -4
	    (-1☓9) = -9
	    (0☓2) = 0
	    (0☓3) = 0
	    (0☓4) = 0
	    (0☓9) = 0
	    (2☓3) = 6
	    ----------------------
	   Resultant pair : 10
	*/
	task->productLessThanK(arr, n, k);
	// Test B
	k = 0;
	/*
	    arr = [ -1, 0, 2, 3 , 4, 9 ]
	    product k = 0   
	    (-1 ☓ 2) = -2
	    (-1 ☓ 3) = -3
	    (-1 ☓ 4) = -4
	    (-1 ☓ 9) = -9
	    -------------------------
	    Resultant pair : 4
	*/
	task->productLessThanK(arr, n, k);
	return 0;
}

 -1 0 2 3 4 9
 K : 7
 Result : 10
 K : 0
 Result : 4

// Include namespace system
using System;
// Csharp program for
// Count pairs in a sorted array whose product is less than k
public class ProductPair
{
	// Display array elements
	public void printArray(int[] arr, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			Console.Write(" " + arr[i]);
		}
	}
	public void productLessThanK(int[] arr, int n, int k)
	{
		int count = 0;
		int start = 0;
		int last = n - 1;
		while (start < last)
		{
			if ((arr[start] * arr[last]) < k)
			{
				// Given array is sorted.
				// And here start and last element product is less than k.
				if (arr[start] < 0 && arr[last] >= 0)
				{
					// When product is combination of two different sign.
					// So we need to checking individual element
					// Current Boundary pair
					count += 1;
					int i = start + 1;
					while (i < last && arr[i] <= 0)
					{
						if (arr[start] * arr[i] < k)
						{
							count += 1;
						}
						i++;
					}
					count += last - i;
				}
				else
				{
					// (last - start) provide number of elements.
					count += (last - start);
				}
				start++;
			}
			else
			{
				last--;
			}
		}
		Console.Write("\n K : " + k);
		// Display calculated result
		Console.Write("\n Result : " + count);
	}
	public static void Main(String[] args)
	{
		ProductPair task = new ProductPair();
		int[] arr = {
			-1 , 0 , 2 , 3 , 4 , 9
		};
		int n = arr.Length;
		// Display given array
		task.printArray(arr, n);
		// Test A
		int k = 7;
		/*
		    arr = [ -1, 0, 2, 3 , 4, 9  ]
		    k = 7 
		    ----------------------
		    (-1☓0) = 0
		    (-1☓2) = -2
		    (-1☓3) = -3
		    (-1☓4) = -4
		    (-1☓9) = -9
		    (0☓2) = 0
		    (0☓3) = 0
		    (0☓4) = 0
		    (0☓9) = 0
		    (2☓3) = 6
		    ----------------------
		   Resultant pair : 10
		*/
		task.productLessThanK(arr, n, k);
		// Test B
		k = 0;
		/*
		    arr = [ -1, 0, 2, 3 , 4, 9 ]
		    product k = 0   
		    (-1 ☓ 2) = -2
		    (-1 ☓ 3) = -3
		    (-1 ☓ 4) = -4
		    (-1 ☓ 9) = -9
		    -------------------------
		    Resultant pair : 4
		*/
		task.productLessThanK(arr, n, k);
	}
}

 -1 0 2 3 4 9
 K : 7
 Result : 10
 K : 0
 Result : 4

package main
import "fmt"
// Go program for
// Count pairs in a sorted array whose product is less than k

// Display array elements
func printArray(arr[] int, n int) {
	for i := 0 ; i < n ; i++ {
		fmt.Print(" ", arr[i])
	}
}
func productLessThanK(arr[] int, n int, k int) {
	var count int = 0
	var start int = 0
	var last int = n - 1
	for (start < last) {
		if (arr[start] * arr[last]) < k {
			// Given array is sorted.
			// And here start and last element product is less than k.
			if arr[start] < 0 && arr[last] >= 0 {
				// When product is combination of two different sign.
				// So we need to checking individual element
				// Current Boundary pair
				count += 1
				var i int = start + 1
				for (i < last && arr[i] <= 0) {
					if arr[start] * arr[i] < k {
						count += 1
					}
					i++
				}
				count += last - i
			} else {
				// (last - start) provide number of elements.
				count += (last - start)
			}
			start++
		} else {
			last--
		}
	}
	fmt.Print("\n K : ", k)
	// Display calculated result
	fmt.Print("\n Result : ", count)
}
func main() {
	
	var arr = [] int {-1, 0, 2, 3, 4, 9}
	var n int = len(arr)
	// Display given array
	printArray(arr, n)
	// Test A
	var k int = 7
	/*
	    arr = [ -1, 0, 2, 3 , 4, 9  ]
	    k = 7 
	    ----------------------
	    (-1☓0) = 0
	    (-1☓2) = -2
	    (-1☓3) = -3
	    (-1☓4) = -4
	    (-1☓9) = -9
	    (0☓2) = 0
	    (0☓3) = 0
	    (0☓4) = 0
	    (0☓9) = 0
	    (2☓3) = 6
	    ----------------------
	   Resultant pair : 10
	*/
	productLessThanK(arr, n, k)
	// Test B
	k = 0
	/*
	    arr = [ -1, 0, 2, 3 , 4, 9 ]
	    product k = 0   
	    (-1 ☓ 2) = -2
	    (-1 ☓ 3) = -3
	    (-1 ☓ 4) = -4
	    (-1 ☓ 9) = -9
	    -------------------------
	    Resultant pair : 4
	*/
	productLessThanK(arr, n, k)
}

 -1 0 2 3 4 9
 K : 7
 Result : 10
 K : 0
 Result : 4

<?php
// Php program for
// Count pairs in a sorted array whose product is less than k
class ProductPair
{
	// Display array elements
	public	function printArray($arr, $n)
	{
		for ($i = 0; $i < $n; ++$i)
		{
			echo(" ".$arr[$i]);
		}
	}
	public	function productLessThanK($arr, $n, $k)
	{
		$count = 0;
		$start = 0;
		$last = $n - 1;
		while ($start < $last)
		{
			if (($arr[$start] * $arr[$last]) < $k)
			{
				// Given array is sorted.
				// And here start and last element product is less than k.
				if ($arr[$start] < 0 && $arr[$last] >= 0)
				{
					// When product is combination of two different sign.
					// So we need to checking individual element
					// Current Boundary pair
					$count += 1;
					$i = $start + 1;
					while ($i < $last && $arr[$i] <= 0)
					{
						if ($arr[$start] * $arr[$i] < $k)
						{
							$count += 1;
						}
						$i++;
					}
					$count += $last - $i;
				}
				else
				{
					// (last - start) provide number of elements.
					$count += ($last - $start);
				}
				$start++;
			}
			else
			{
				$last--;
			}
		}
		echo("\n K : ".$k);
		// Display calculated result
		echo("\n Result : ".$count);
	}
}

function main()
{
	$task = new ProductPair();
	$arr = array(-1, 0, 2, 3, 4, 9);
	$n = count($arr);
	// Display given array
	$task->printArray($arr, $n);
	// Test A
	$k = 7;
	/*
	    arr = [ -1, 0, 2, 3 , 4, 9  ]
	    k = 7 
	    ----------------------
	    (-1☓0) = 0
	    (-1☓2) = -2
	    (-1☓3) = -3
	    (-1☓4) = -4
	    (-1☓9) = -9
	    (0☓2) = 0
	    (0☓3) = 0
	    (0☓4) = 0
	    (0☓9) = 0
	    (2☓3) = 6
	    ----------------------
	   Resultant pair : 10
	*/
	$task->productLessThanK($arr, $n, $k);
	// Test B
	$k = 0;
	/*
	    arr = [ -1, 0, 2, 3 , 4, 9 ]
	    product k = 0   
	    (-1 ☓ 2) = -2
	    (-1 ☓ 3) = -3
	    (-1 ☓ 4) = -4
	    (-1 ☓ 9) = -9
	    -------------------------
	    Resultant pair : 4
	*/
	$task->productLessThanK($arr, $n, $k);
}
main();

 -1 0 2 3 4 9
 K : 7
 Result : 10
 K : 0
 Result : 4

// Node JS program for
// Count pairs in a sorted array whose product is less than k
class ProductPair
{
	// Display array elements
	printArray(arr, n)
	{
		for (var i = 0; i < n; ++i)
		{
			process.stdout.write(" " + arr[i]);
		}
	}
	productLessThanK(arr, n, k)
	{
		var count = 0;
		var start = 0;
		var last = n - 1;
		while (start < last)
		{
			if ((arr[start] * arr[last]) < k)
			{
				// Given array is sorted.
				// And here start and last element product is less than k.
				if (arr[start] < 0 && arr[last] >= 0)
				{
					// When product is combination of two different sign.
					// So we need to checking individual element
					// Current Boundary pair
					count += 1;
					var i = start + 1;
					while (i < last && arr[i] <= 0)
					{
						if (arr[start] * arr[i] < k)
						{
							count += 1;
						}
						i++;
					}
					count += last - i;
				}
				else
				{
					// (last - start) provide number of elements.
					count += (last - start);
				}
				start++;
			}
			else
			{
				last--;
			}
		}
		process.stdout.write("\n K : " + k);
		// Display calculated result
		process.stdout.write("\n Result : " + count);
	}
}

function main()
{
	var task = new ProductPair();
	var arr = [-1, 0, 2, 3, 4, 9];
	var n = arr.length;
	// Display given array
	task.printArray(arr, n);
	// Test A
	var k = 7;
	/*
	    arr = [ -1, 0, 2, 3 , 4, 9  ]
	    k = 7 
	    ----------------------
	    (-1☓0) = 0
	    (-1☓2) = -2
	    (-1☓3) = -3
	    (-1☓4) = -4
	    (-1☓9) = -9
	    (0☓2) = 0
	    (0☓3) = 0
	    (0☓4) = 0
	    (0☓9) = 0
	    (2☓3) = 6
	    ----------------------
	   Resultant pair : 10
	*/
	task.productLessThanK(arr, n, k);
	// Test B
	k = 0;
	/*
	    arr = [ -1, 0, 2, 3 , 4, 9 ]
	    product k = 0   
	    (-1 ☓ 2) = -2
	    (-1 ☓ 3) = -3
	    (-1 ☓ 4) = -4
	    (-1 ☓ 9) = -9
	    -------------------------
	    Resultant pair : 4
	*/
	task.productLessThanK(arr, n, k);
}
main();

 -1 0 2 3 4 9
 K : 7
 Result : 10
 K : 0
 Result : 4

#  Python 3 program for
#  Count pairs in a sorted array whose product is less than k
class ProductPair :
	#  Display list elements
	def printArray(self, arr, n) :
		i = 0
		while (i < n) :
			print(" ", arr[i], end = "")
			i += 1
		
	
	def productLessThanK(self, arr, n, k) :
		count = 0
		start = 0
		last = n - 1
		while (start < last) :
			if ((arr[start] * arr[last]) < k) :
				#  Given list is sorted.
				#  And here start and last element product is less than k.
				if (arr[start] < 0 and arr[last] >= 0) :
					#  When product is combination of two different sign.
					#  So we need to checking individual element
					#  Current Boundary pair
					count += 1
					i = start + 1
					while (i < last and arr[i] <= 0) :
						if (arr[start] * arr[i] < k) :
							count += 1
						
						i += 1
					
					count += last - i
				else :
					#  (last - start) provide number of elements.
					count += (last - start)
				
				start += 1
			else :
				last -= 1
			
		
		print("\n K : ", k, end = "")
		#  Display calculated result
		print("\n Result : ", count, end = "")
	

def main() :
	task = ProductPair()
	arr = [-1, 0, 2, 3, 4, 9]
	n = len(arr)
	#  Display given list
	task.printArray(arr, n)
	#  Test A
	k = 7
	#    arr = [ -1, 0, 2, 3 , 4, 9  ]
	#    k = 7 
	#    ----------------------
	#    (-1☓0) = 0
	#    (-1☓2) = -2
	#    (-1☓3) = -3
	#    (-1☓4) = -4
	#    (-1☓9) = -9
	#    (0☓2) = 0
	#    (0☓3) = 0
	#    (0☓4) = 0
	#    (0☓9) = 0
	#    (2☓3) = 6
	#    ----------------------
	#   Resultant pair : 10
	task.productLessThanK(arr, n, k)
	#  Test B
	k = 0
	#    arr = [ -1, 0, 2, 3 , 4, 9 ]
	#    product k = 0   
	#    (-1 ☓ 2) = -2
	#    (-1 ☓ 3) = -3
	#    (-1 ☓ 4) = -4
	#    (-1 ☓ 9) = -9
	#    -------------------------
	#    Resultant pair : 4
	task.productLessThanK(arr, n, k)

if __name__ == "__main__": main()

  -1  0  2  3  4  9
 K :  7
 Result :  10
 K :  0
 Result :  4

#  Ruby program for
#  Count pairs in a sorted array whose product is less than k
class ProductPair 
	#  Display array elements
	def printArray(arr, n) 
		i = 0
		while (i < n) 
			print(" ", arr[i])
			i += 1
		end

	end

	def productLessThanK(arr, n, k) 
		count = 0
		start = 0
		last = n - 1
		while (start < last) 
			if ((arr[start] * arr[last]) < k) 
				#  Given array is sorted.
				#  And here start and last element product is less than k.
				if (arr[start] < 0 && arr[last] >= 0) 
					#  When product is combination of two different sign.
					#  So we need to checking individual element
					#  Current Boundary pair
					count += 1
					i = start + 1
					while (i < last && arr[i] <= 0) 
						if (arr[start] * arr[i] < k) 
							count += 1
						end

						i += 1
					end

					count += last - i
				else
 
					#  (last - start) provide number of elements.
					count += (last - start)
				end

				start += 1
			else
 
				last -= 1
			end

		end

		print("\n K : ", k)
		#  Display calculated result
		print("\n Result : ", count)
	end

end

def main() 
	task = ProductPair.new()
	arr = [-1, 0, 2, 3, 4, 9]
	n = arr.length
	#  Display given array
	task.printArray(arr, n)
	#  Test A
	k = 7
	#    arr = [ -1, 0, 2, 3 , 4, 9  ]
	#    k = 7 
	#    ----------------------
	#    (-1☓0) = 0
	#    (-1☓2) = -2
	#    (-1☓3) = -3
	#    (-1☓4) = -4
	#    (-1☓9) = -9
	#    (0☓2) = 0
	#    (0☓3) = 0
	#    (0☓4) = 0
	#    (0☓9) = 0
	#    (2☓3) = 6
	#    ----------------------
	#   Resultant pair : 10
	task.productLessThanK(arr, n, k)
	#  Test B
	k = 0
	#    arr = [ -1, 0, 2, 3 , 4, 9 ]
	#    product k = 0   
	#    (-1 ☓ 2) = -2
	#    (-1 ☓ 3) = -3
	#    (-1 ☓ 4) = -4
	#    (-1 ☓ 9) = -9
	#    -------------------------
	#    Resultant pair : 4
	task.productLessThanK(arr, n, k)
end

main()

 -1 0 2 3 4 9
 K : 7
 Result : 10
 K : 0
 Result : 4

// Scala program for
// Count pairs in a sorted array whose product is less than k
class ProductPair()
{
	// Display array elements
	def printArray(arr: Array[Int], n: Int): Unit = {
		var i: Int = 0;
		while (i < n)
		{
			print(" " + arr(i));
			i += 1;
		}
	}
	def productLessThanK(arr: Array[Int], n: Int, k: Int): Unit = {
		var count: Int = 0;
		var start: Int = 0;
		var last: Int = n - 1;
		while (start < last)
		{
			if ((arr(start) * arr(last)) < k)
			{
				// Given array is sorted.
				// And here start and last element product is less than k.
				if (arr(start) < 0 && arr(last) >= 0)
				{
					// When product is combination of two different sign.
					// So we need to checking individual element
					// Current Boundary pair
					count += 1;
					var i: Int = start + 1;
					while (i < last && arr(i) <= 0)
					{
						if (arr(start) * arr(i) < k)
						{
							count += 1;
						}
						i += 1;
					}
					count += last - i;
				}
				else
				{
					// (last - start) provide number of elements.
					count += (last - start);
				}
				start += 1;
			}
			else
			{
				last -= 1;
			}
		}
		print("\n K : " + k);
		// Display calculated result
		print("\n Result : " + count);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: ProductPair = new ProductPair();
		var arr: Array[Int] = Array(-1, 0, 2, 3, 4, 9);
		var n: Int = arr.length;
		// Display given array
		task.printArray(arr, n);
		// Test A
		var k: Int = 7;
		/*
		    arr = [ -1, 0, 2, 3 , 4, 9  ]
		    k = 7 
		    ----------------------
		    (-1☓0) = 0
		    (-1☓2) = -2
		    (-1☓3) = -3
		    (-1☓4) = -4
		    (-1☓9) = -9
		    (0☓2) = 0
		    (0☓3) = 0
		    (0☓4) = 0
		    (0☓9) = 0
		    (2☓3) = 6
		    ----------------------
		   Resultant pair : 10
		*/
		task.productLessThanK(arr, n, k);
		// Test B
		k = 0;
		/*
		    arr = [ -1, 0, 2, 3 , 4, 9 ]
		    product k = 0   
		    (-1 ☓ 2) = -2
		    (-1 ☓ 3) = -3
		    (-1 ☓ 4) = -4
		    (-1 ☓ 9) = -9
		    -------------------------
		    Resultant pair : 4
		*/
		task.productLessThanK(arr, n, k);
	}
}

 -1 0 2 3 4 9
 K : 7
 Result : 10
 K : 0
 Result : 4

import Foundation;
// Swift 4 program for
// Count pairs in a sorted array whose product is less than k
class ProductPair
{
	// Display array elements
	func printArray(_ arr: [Int], _ n: Int)
	{
		var i: Int = 0;
		while (i < n)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
	}
	func productLessThanK(_ arr: [Int], _ n: Int, _ k: Int)
	{
		var count: Int = 0;
		var start: Int = 0;
		var last: Int = n - 1;
		while (start < last)
		{
			if ((arr[start] * arr[last]) < k)
			{
				// Given array is sorted.
				// And here start and last element product is less than k.
				if (arr[start] < 0 && arr[last] >= 0)
				{
					// When product is combination of two different sign.
					// So we need to checking individual element
					// Current Boundary pair
					count += 1;
					var i: Int = start + 1;
					while (i < last && arr[i] <= 0)
					{
						if (arr[start] * arr[i] < k)
						{
							count += 1;
						}
						i += 1;
					}
					count += last - i;
				}
				else
				{
					// (last - start) provide number of elements.
					count += (last - start);
				}
				start += 1;
			}
			else
			{
				last -= 1;
			}
		}
		print("\n K : ", k, terminator: "");
		// Display calculated result
		print("\n Result : ", count, terminator: "");
	}
}
func main()
{
	let task: ProductPair = ProductPair();
	let arr: [Int] = [-1, 0, 2, 3, 4, 9];
	let n: Int = arr.count;
	// Display given array
	task.printArray(arr, n);
	// Test A
	var k: Int = 7;
	/*
	    arr = [ -1, 0, 2, 3 , 4, 9  ]
	    k = 7 
	    ----------------------
	    (-1☓0) = 0
	    (-1☓2) = -2
	    (-1☓3) = -3
	    (-1☓4) = -4
	    (-1☓9) = -9
	    (0☓2) = 0
	    (0☓3) = 0
	    (0☓4) = 0
	    (0☓9) = 0
	    (2☓3) = 6
	    ----------------------
	   Resultant pair : 10
	*/
	task.productLessThanK(arr, n, k);
	// Test B
	k = 0;
	/*
	    arr = [ -1, 0, 2, 3 , 4, 9 ]
	    product k = 0   
	    (-1 ☓ 2) = -2
	    (-1 ☓ 3) = -3
	    (-1 ☓ 4) = -4
	    (-1 ☓ 9) = -9
	    -------------------------
	    Resultant pair : 4
	*/
	task.productLessThanK(arr, n, k);
}
main();

  -1  0  2  3  4  9
 K :  7
 Result :  10
 K :  0
 Result :  4

// Kotlin program for
// Count pairs in a sorted array whose product is less than k
class ProductPair
{
	// Display array elements
	fun printArray(arr: Array < Int > , n: Int): Unit
	{
		var i: Int = 0;
		while (i < n)
		{
			print(" " + arr[i]);
			i += 1;
		}
	}
	fun productLessThanK(arr: Array < Int > , n: Int, k: Int): Unit
	{
		var count: Int = 0;
		var start: Int = 0;
		var last: Int = n - 1;
		while (start < last)
		{
			if ((arr[start] * arr[last]) < k)
			{
				// Given array is sorted.
				// And here start and last element product is less than k.
				if (arr[start] < 0 && arr[last] >= 0)
				{
					// When product is combination of two different sign.
					// So we need to checking individual element
					// Current Boundary pair
					count += 1;
					var i: Int = start + 1;
					while (i < last && arr[i] <= 0)
					{
						if (arr[start] * arr[i] < k)
						{
							count += 1;
						}
						i += 1;
					}
					count += last - i;
				}
				else
				{
					// (last - start) provide number of elements.
					count += (last - start);
				}
				start += 1;
			}
			else
			{
				last -= 1;
			}
		}
		print("\n K : " + k);
		// Display calculated result
		print("\n Result : " + count);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: ProductPair = ProductPair();
	val arr: Array < Int > = arrayOf(-1, 0, 2, 3, 4, 9);
	val n: Int = arr.count();
	// Display given array
	task.printArray(arr, n);
	// Test A
	var k: Int = 7;
	/*
	    arr = [ -1, 0, 2, 3 , 4, 9  ]
	    k = 7 
	    ----------------------
	    (-1☓0) = 0
	    (-1☓2) = -2
	    (-1☓3) = -3
	    (-1☓4) = -4
	    (-1☓9) = -9
	    (0☓2) = 0
	    (0☓3) = 0
	    (0☓4) = 0
	    (0☓9) = 0
	    (2☓3) = 6
	    ----------------------
	   Resultant pair : 10
	*/
	task.productLessThanK(arr, n, k);
	// Test B
	k = 0;
	/*
	    arr = [ -1, 0, 2, 3 , 4, 9 ]
	    product k = 0   
	    (-1 ☓ 2) = -2
	    (-1 ☓ 3) = -3
	    (-1 ☓ 4) = -4
	    (-1 ☓ 9) = -9
	    -------------------------
	    Resultant pair : 4
	*/
	task.productLessThanK(arr, n, k);
}

 -1 0 2 3 4 9
 K : 7
 Result : 10
 K : 0
 Result : 4

Time Complexity Analysis

The productLessThanK function iterates through the array once, so it has a linear time complexity of O(n), where n is the number of elements in the array.