Smallest index in the given array that satisfies the given condition
Given an array arr[] of size N and an integer K, the task is to find the smallest index in the array such that:
floor(arr[i] / 1) + floor(arr[i + 1] / 2) + floor(arr[i + 2] / 3) + ….. + floor(arr[n – 1] / n – i ) ? K
If no such index is found then print -1.
Examples:
Input: arr[] = {6, 5, 4, 2}, K = 8
Output: 1
(6 / 1) + (5 / 2) + (4 / 3) + (2 / 4) = 6 + 2 + 1 + 0 = 9 which is > K
(5 / 1) + (4 / 2) + (2 / 3) = 5 + 2 + 0 = 7 < K
Hence i = 1 is the required index.
Input: arr[] = {5, 4, 2, 3, 9, 1, 8, 7}, K = 7
Output: 5
Approach: For every index i starting from 0, find the sum of the given series, and the first index which given a sum greater than or equal to K is our required index. If there is no such index then print -1.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the required index int getIndex( int arr[], int n, int K) { // Check all the indices, the first index // satisfying the condition is // the required index for ( int i = 0; i < n; i++) { // To store the sum of the series int sum = 0; // Denominator for the sum series int den = 1; // Find the sum of the series for ( int j = i; j < n; j++) { sum += (arr[j] / den); // Increment the denominator den++; // If current sum is greater than K // no need to execute loop further if (sum > K) break ; } // Found the first valid index if (sum <= K) return i; } return -1; } // Driver code int main() { int arr[] = { 6, 5, 4, 2 }; int n = sizeof (arr) / sizeof (arr[0]); int K = 8; cout << getIndex(arr, n, K); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return the required index static int getIndex( int arr[], int n, int K) { // Check all the indices, the first index // satisfying the condition is // the required index for ( int i = 0 ; i < n; i++) { // To store the sum of the series int sum = 0 ; // Denominator for the sum series int den = 1 ; // Find the sum of the series for ( int j = i; j < n; j++) { sum += (arr[j] / den); // Increment the denominator den++; // If current sum is greater than K // no need to execute loop further if (sum > K) break ; } // Found the first valid index if (sum <= K) return i; } return - 1 ; } // Driver code public static void main(String[] args) { int arr[] = { 6 , 5 , 4 , 2 }; int n = arr.length; int K = 8 ; System.out.print(getIndex(arr, n, K)); } } |
Python
# Python3 implementation of the approach def getIndex(array, k): n = len (array) for ind in range (n): sum = 0 div = 1 for item in array: sum + = item / / div div + = 1 if sum > k: break if sum < = k: return ind return - 1 # Driver code arr = [ 6 , 5 , 4 , 2 ] K = 8 print (getIndex(arr, K)) arr = [ 5 , 4 , 2 , 3 , 9 , 1 , 8 , 7 ] K = 7 print (getIndex(arr, K)) |
C#
// C# implementation of the approach using System; class GFG { // Function to return the required index static int getIndex( int []arr, int n, int K) { // Check all the indices, the first index // satisfying the condition is // the required index for ( int i = 0; i < n; i++) { // To store the sum of the series int sum = 0; // Denominator for the sum series int den = 1; // Find the sum of the series for ( int j = i; j < n; j++) { sum += (arr[j] / den); // Increment the denominator den++; // If current sum is greater than K // no need to execute loop further if (sum > K) break ; } // Found the first valid index if (sum <= K) return i; } return -1; } // Driver code static public void Main () { int []arr = { 6, 5, 4, 2 }; int n = arr.Length; int K = 8; Console.WriteLine(getIndex(arr, n, K)); } } // This Code is contributed by ajit. |
PHP
<?php // PHP implementation of the approach // Function to return the required index function getIndex( $arr , $n , $K ) { // Check all the indices, the first // index satisfying the condition is // the required index for ( $i = 0; $i < $n ; $i ++) { // To store the sum of the series $sum = 0; // Denominator for the sum series $den = 1; // Find the sum of the series for ( $j = $i ; $j < $n ; $j ++) { $sum += floor ( $arr [ $j ] / $den ); // Increment the denominator $den ++; // If current sum is greater than K // no need to execute loop further if ( $sum > $K ) break ; } // Found the first valid index if ( $sum <= $K ) return $i ; } return -1; } // Driver code $arr = array ( 6, 5, 4, 2 ); $n = sizeof( $arr ); $K = 8; echo getIndex( $arr , $n , $K ); // This code is contributed by Ryuga ?> |
Javascript
<script> // Javascript implementation of the approach // Function to return the required index function getIndex(arr, n, K) { // Check all the indices, the first index // satisfying the condition is // the required index for (let i = 0; i < n; i++) { // To store the sum of the series let sum = 0; // Denominator for the sum series let den = 1; // Find the sum of the series for (let j = i; j < n; j++) { sum += parseInt((arr[j] / den), 10); // Increment the denominator den++; // If current sum is greater than K // no need to execute loop further if (sum > K) break ; } // Found the first valid index if (sum <= K) return i; } return -1; } let arr = [ 6, 5, 4, 2 ]; let n = arr.length; let K = 8; document.write(getIndex(arr, n, K)); </script> |
1
Time complexity: O(N2)
Auxiliary space: O(1)
Contact Us