how to reduce time complexity of nested loop or replace nested loop

2 posts Sat, May 21, 2022 at 11:13 PM in General Discussion

Hi experts,

I tried to resolve the issue here, but my solution exceeded 3s for 3 cases. Can you all please suggest?

HERE IS THE PROBLEM:

Given an array a of positive integers, find the number of pairs of integers for which the difference between the two numbers is equal to a given number k. Since the number of pairs could be quite large, take it modulo 109 + 7 for your output.

Example

For k = 3 and a = [1, 6, 8, 2, 4, 9, 12], the output should be
solution(k, a) = 3.

There are three pairs of integers whose difference is equal to 3: (1, 4), (6, 9) and (9, 12).

Input/Output

[execution time limit] 3 seconds (java)

[input] integer k

The specified difference between two numbers.

Guaranteed constraints:
1 ≤ k ≤ 1000.

[input] array.integer a

Guaranteed constraints:
1 ≤ a.length ≤ 105,
1 ≤ a[i] ≤ 1000.

[output] integer

The number of pairs of integers with difference k modulo 109 + 7.

[Java] Syntax Tips

// Prints help message to the console
// Returns a string
//
// Globals declared here will cause a compilation error,
// declare variables inside the function instead!
String helloWorld(String name) {
System.out.println("This prints to the console when you Run Tests");
return "Hello, " + name;
}

===================================

Here's my solution:

int solution(int k, int[] a) {

int number = 0;

for(int i=0; i<a.length; i++)
{
for(int j=i+1; j<a.length; j++)
{
if(Math.abs(a[i]-a[j])==k)
number++;
}
}

return number;

}

View: Threaded  |  Flat
+0
Sign In or Register to comment.