Count of K-length subarray with each element less than X times the next one
Given an array A[] of length N and two integers X and K, The task is to count the number of indices i (0 ≤ i < N−k) such that:
X0⋅ai < X1⋅ai + 1 < X2⋅ai+2 < . . . < Xk⋅ai+k.
Examples:
Input: A[] = {9, 5, 3, 4, 1}, X = 4, K = 1.
Output: 3.
Explanation: Three Subarrays satisfy the conditions:
i = 0: the subarray [a0, a1] = [9, 5] and 1.9 < 4.5.
i = 1: the subarray [a1, a2] = [5, 3] and 1.5 < 4.3.
i = 2: the subarray [a2, a3] = [3, 2] and 1.3 < 4.4.
i = 3: the subarray [a3, a4] = [2, 1] but 1.4 = 4.1, so this subarray doesn’t satisfy the condition.Input: A[] = {22, 12, 16, 4, 3, 22, 12}, X = 2, K = 3.
Output: 1
Explanation: There are total 4 subarray out of which 1 satisfy the given condition.
i = 0: the subarray [a0, a1, a2, a3] = [22, 12, 16, 4] and 1.22 < 2.12 < 4.16 > 8.4, so this subarray doesn’t satisfy the condition.
i = 1: the subarray [a1, a2, a3, a4]=[12, 16, 4, 3] and 1.12 < 2.16 > 4.4 < 8.3, so this subarray doesn’t satisfy the condition.
i = 2: the subarray [a2, a3, a4, a5]=[16, 4, 3, 22] and 1.16 > 2.4 < 4.8 < 8.22, so this subarray doesn’t satisfy the condition.
i = 3: the subarray [a3, a4, a5, a6]=[4, 3, 22, 12] and 1.4 < 2.3 < 4.22 < 8.12, so this subarray satisfies the condition.
Naive Approach: To solve the problem follow the below idea.
Find all the subarray of length K+1 and such that every element in the subarray is X times smaller than its next element in the subarray .
Follow the steps below to implement the idea:
- Run a for loop from i = 0 to i < N-(K+1). In each iteration:
- Run a for loop from i to i+K and trace that every element in this subarray is X times smaller than the next element.
- After termination of the loop if every element in this loop is X times smaller than the next element increment ans variable by 1.
- Print the answer.
Below is the implementation for the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function performing Calculation int solve( int a[], int n, int k, int X) { int ans = 0; for ( int i = 0; i < n - (k + 1); i++) { bool flag = true ; for ( int j = i; j < k; j++) { if (a[j] < X * a[j + 1]) continue ; else { flag = false ; } } if (flag) ans++; } return ans; } // Driver Code int main() { int A[] = { 9, 5, 3, 4, 1 }; int N = sizeof (A) / sizeof (A[0]); int K = 1, X = 4; // Function Call cout << solve(A, N, K, X); return 0; } |
Java
// Java code to implement the approach import java.io.*; class GFG { // Function performing Calculation static int solve( int [] a, int n, int k, int X) { int ans = 0 ; for ( int i = 0 ; i < n - (k + 1 ); i++) { boolean flag = true ; for ( int j = i; j < k; j++) { if (a[j] < X * a[j + 1 ]) { continue ; } else { flag = false ; } } if (flag) { ans++; } } return ans; } public static void main(String[] args) { int [] A = { 9 , 5 , 3 , 4 , 1 }; int N = A.length; int K = 1 , X = 4 ; // Function call System.out.print(solve(A, N, K, X)); } } // This code is contributed by lokesh (lokeshmvs21). |
Python3
# Python code to implement the approach # Function performing Calculation def solve(a, n, k, X): ans = 0 for i in range (n - (k + 1 )): flag = True for j in range (i, k): if a[j] < X * a[j + 1 ]: continue else : flag = False if flag: ans + = 1 return ans # Driver Code A = [ 9 , 5 , 3 , 4 , 1 ] N = len (A) K = 1 X = 4 # Function Call print (solve(A, N, K, X)) # This code is contributed by Tapesh(tapeshdua420) |
C#
// C# code to implement the approach using System; using System.Collections.Generic; public class GFG{ // Function performing Calculation static int solve( int [] a, int n, int k, int X) { int ans = 0; for ( int i = 0; i < n - (k + 1); i++) { bool flag = true ; for ( int j = i; j < k; j++) { if (a[j] < X * a[j + 1]) { continue ; } else { flag = false ; } } if (flag) { ans++; } } return ans; } // Driver Code static public void Main (){ int [] A = { 9, 5, 3, 4, 1 }; int N = A.Length; int K = 1, X = 4; // Function call Console.WriteLine(solve(A, N, K, X)); } } // This code is contributed by sanjoy_62. |
Javascript
<script> // Javascript code to implement the approach // Function performing Calculation function solve(a, n, k, X) { let ans = 0; for (let i = 0; i < n - (k + 1); i++) { let flag = true ; for (let j = i; j < k; j++) { if (a[j] < X * a[j + 1]) continue ; else { flag = false ; } } if (flag) ans++; } return ans; } // Driver Code let A = [ 9, 5, 3, 4, 1 ]; let N = A.length; let K = 1, X = 4; // Function Call document.write(solve(A, N, K, X)); // This code is contributed by satwik4409. </script> |
3
Time complexity: O(N * K)
Auxiliary Space: O(1).
Efficient Approach: To solve the problem follow the below idea.
Using two pointer approach and checking if every element in the subarray is 4 times smaller than its next element and then moving the window forward till the last element is reached.
Follow the steps below to implement the idea:
- Run a while loop from j = 0 to j < N – 1. In each iteration:
- Check if the length of window is equal to K + 1 (i.e j – i + 1 = k + 1) then increment answer by 1.
- If jth element is less than X times (j + 1)th element (A[j] < X*A[j + 1]) then increment j by 1 otherwise move i pointer to j since no subarray that contains jth and (j+1)th element together can satisfy the given condition.
- Print the answer.
Below is the implementation for the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function performing Calculation int solve( int a[], int n, int k, int X) { int ans = 0; int i = 0, j = 0; // Loop to utilize the sliding window concept while (j < n - 1) { if (j - i + 1 == k + 1) { i++; ans++; } if (a[j] < a[j + 1] * X) { j++; } else { i = j; j++; } } return ans; } // Driver Code int main() { int A[] = { 9, 5, 3, 4, 1 }; int N = sizeof (A) / sizeof (A[0]); int K = 1, X = 4; // Function Call cout << solve(A, N, K, X); return 0; } |
Java
// JAVA code to implement the approach import java.util.*; class GFG { // Function performing Calculation public static int solve( int a[], int n, int k, int X) { int ans = 0 ; int i = 0 , j = 0 ; // Loop to utilize the sliding window concept while (j < n - 1 ) { if (j - i + 1 == k + 1 ) { i++; ans++; } if (a[j] < a[j + 1 ] * X) { j++; } else { i = j; j++; } } return ans; } // Driver Code public static void main(String[] args) { int A[] = { 9 , 5 , 3 , 4 , 1 }; int N = A.length; int K = 1 , X = 4 ; // Function Call System.out.print(solve(A, N, K, X)); } } // This code is contributed by Taranpreet |
Python3
# Python code to implement the approach # Function performing Calculation def solve(a, n, k, X): ans = 0 for i in range (n - (k + 1 )): flag = True for j in range (i, k): if a[j] < X * a[j + 1 ]: continue else : flag = False if flag: ans + = 1 return ans if __name__ = = '__main__' : A = [ 9 , 5 , 3 , 4 , 1 ] N = len (A) K = 1 X = 4 # Function Call print (solve(A, N, K, X)) # This code is contributed by Tapesh(tapeshdua420) |
C#
// C# code to implement the approach using System; class GFG { // Function performing Calculation public static int solve( int [] a, int n, int k, int X) { int ans = 0; int i = 0, j = 0; // Loop to utilize the sliding window concept while (j < n - 1) { if (j - i + 1 == k + 1) { i++; ans++; } if (a[j] < a[j + 1] * X) { j++; } else { i = j; j++; } } return ans; } // Driver Code public static void Main( string [] args) { int [] A = { 9, 5, 3, 4, 1 }; int N = A.Length; int K = 1, X = 4; // Function Call Console.WriteLine(solve(A, N, K, X)); } } // This code is contributed by Tapesh(tapeshdua420) |
Javascript
<script> // JavaScript code to implement the approach // Function performing Calculation const solve = (a, n, k, X) => { let ans = 0; let i = 0, j = 0; // Loop to utilize the sliding window concept while (j < n - 1) { if (j - i + 1 == k + 1) { i++; ans++; } if (a[j] < a[j + 1] * X) { j++; } else { i = j; j++; } } return ans; } // Driver Code let A = [9, 5, 3, 4, 1]; let N = A.length; let K = 1, X = 4; // Function Call document.write(solve(A, N, K, X)); // This code is contributed by rakeshsahni </script> |
3
Time Complexity: O(N)
Auxiliary Space: O(1)