|
Given three integers N, V, I and an integer array nums[], find if there exists a pair of indices i, j (i < j) such that (j – i) <= I and abs(arr[j] – arr[i]) <= V. Print “Yes” if such a pair exists, else print “No”.
Examples:
Input:N = 6, V = 2, I = 1, nums = [4, 7, 3, 2, 9, 1]
Output: Yes
Explanation: In the given array pair index (2,3) has a difference of 1 which is less than I and abs(nums[2] – nums[3]) <= V, hence there exists a pair, and the program will return ‘Yes’
Input:N = 6, V = 5, I = 3, nums = [4, 7, 3, 2, 9, 1]
Output: Yes
Explanation: In the given array pair index (0,1) has a difference of 1 which is less than I and abs(nums[0] – nums[1]) <= V, hence there exists a pair, and the program will return ‘Yes’
Approach: To solve the problem follow the below steps:
- Run an outer loop to iterate from 0 to n-1 index (0 <= i < n)
- Run a inner loop for j which runs from i+1 to i+1+I index (i+1 <= j < i+1+I)
- In the inner loop check the condition abs(nums[i] – nums[j]) <= V
- If the condition in step 3 is true return True
- If no pairs are found after iterating all the pairs we return a False
Below is the implementation of the approach:
C++
#include <iostream>
using namespace std;
bool solve(int nums[], int N, int V, int I) {
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j <= i + I && j < N; ++j) {
if (abs(nums[i] - nums[j]) <= V) {
return true;
}
}
}
return false;
}
int main() {
int N = 6;
int V = 2;
int I = 1;
int arr[] = {4, 7, 3, 2, 9, 1};
if (solve(arr, N, V, I)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}
// Java Implementation
import java.util.Arrays;
public class Main {
public static boolean solve(int[] nums, int N, int V, int I) {
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j <= i + I && j < N; ++j) {
if (Math.abs(nums[i] - nums[j]) <= V) {
return true;
}
}
}
return false;
}
public static void main(String[] args) {
int N = 6;
int V = 2;
int I = 1;
int[] arr = {4, 7, 3, 2, 9, 1};
if (solve(arr, N, V, I)) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
}
// This code is contributed by Tapesh(tapeshdua420)
def solve(nums, N, V, I):
for i in range(N):
for j in range(i+1, i+1+I):
if abs(nums[i]-nums[j]) <= V:
return True
return False
# Driver Code
N = 6
V = 2
I = 1
arr = [4, 7, 3, 2, 9, 1]
if solve(arr, N, V, I):
print('Yes')
else:
print('No')
using System;
public class GFG
{
// Function to solve the problem
public static bool Solve(int[] nums, int N, int V, int I)
{
// Loop through the array elements
for (int i = 0; i < N; ++i)
{
// Check adjacent elements within the given range I
for (int j = i + 1; j <= i + I && j < N; ++j)
{
// Check if the absolute difference between elements is less than or equal to V
if (Math.Abs(nums[i] - nums[j]) <= V)
{
// If condition is met, return true
return true;
}
}
}
// If no such pair is found, return false
return false;
}
// Main method to test the Solve function
public static void Main(string[] args)
{
// Input values
int N = 6;
int V = 2;
int I = 1;
int[] arr = { 4, 7, 3, 2, 9, 1 };
// Call the Solve function and print the result
if (Solve(arr, N, V, I))
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
// Javascript code for the above approach
function solve(nums, N, V, I) {
for (let i = 0; i < N; i++) {
for (let j = i + 1; j < i + 1 + I; j++) {
if (Math.abs(nums[i] - nums[j]) <= V) {
return true
}
}
}
return false
}
// Driver Code
let N = 6
let V = 2
let I = 1
let arr = [4, 7, 3, 2, 9, 1]
if (solve(arr, N, V, I)) {
console.log('Yes')
} else {
console.log('No')
}
// This code is contributed by ragul21
Time Complexity: O(N*I)
Auxiliary Space: O(1)
|
