Given an array arr[] and a number K. The task is to find out the number of valid positions i such that (arr[i] + K) is greater than sum of all elements of array excluding arr[i].
Examples:
Input: arr[] = {2, 1, 6, 7} K = 4
Output: 1
Explanation: There is only 1 valid position i.e 4th.
After adding 4 to the element at 4th position
it is greater than the sum of all other
elements of the array.
Input: arr[] = {2, 1, 5, 4} K = 2
Output: 0
Explanation: There is no valid position.
Approach:
- First of all find the sum of all the elements of the array and store it in a variable say sum.
- Now, traverse the array and for every position i check if the condition (arr[i] + K) > (sum – arr[i]) holds.
- If YES then increase the counter and finally print the value of counter.
Below is the implementation of the above approach:
C++
// C++ program to implement above approach#include <bits/stdc++.h>using namespace std;// Function that will find out// the valid positionint validPosition(int arr[], int N, int K){ int count = 0, sum = 0; // find sum of all the elements for (int i = 0; i < N; i++) { sum += arr[i]; } // adding K to the element and check // whether it is greater than sum of // all other elements for (int i = 0; i < N; i++) { if ((arr[i] + K) > (sum - arr[i])) count++; } return count;}// Driver codeint main(){ int arr[] = { 2, 1, 6, 7 }, K = 4; int N = sizeof(arr) / sizeof(arr[0]); cout << validPosition(arr, N, K); return 0;} |
Java
// Java implementation of the approachclass GFG {// Function that will find out// the valid positionstatic int validPosition(int arr[], int N, int K){ int count = 0, sum = 0; // find sum of all the elements for (int i = 0; i < N; i++) { sum += arr[i]; } // adding K to the element and check // whether it is greater than sum of // all other elements for (int i = 0; i < N; i++) { if ((arr[i] + K) > (sum - arr[i])) count++; } return count;}// Driver codepublic static void main(String[] args){ int arr[] = { 2, 1, 6, 7 }, K = 4; int N = arr.length; System.out.println(validPosition(arr, N, K));}}/* This code contributed by PrinciRaj1992 */ |
Python3
# Python3 program to implement # above approach # Function that will find out # the valid position def validPosition(arr, N, K): count = 0; sum = 0; # find sum of all the elements for i in range(N): sum += arr[i]; # adding K to the element and check # whether it is greater than sum of # all other elements for i in range(N): if ((arr[i] + K) > (sum - arr[i])): count += 1; return count; # Driver code arr = [2, 1, 6, 7 ];K = 4; N = len(arr); print(validPosition(arr, N, K)); # This code is contributed by 29AjayKumar |
C#
// C# implementation of the approachusing System; class GFG { // Function that will find out// the valid positionstatic int validPosition(int []arr, int N, int K){ int count = 0, sum = 0; // find sum of all the elements for (int i = 0; i < N; i++) { sum += arr[i]; } // adding K to the element and check // whether it is greater than sum of // all other elements for (int i = 0; i < N; i++) { if ((arr[i] + K) > (sum - arr[i])) count++; } return count;} // Driver codepublic static void Main(String[] args){ int []arr = { 2, 1, 6, 7 };int K = 4; int N = arr.Length; Console.WriteLine(validPosition(arr, N, K));}}// This code has been contributed by 29AjayKumar |
PHP
<?php// PHP program to implement above approach // Function that will find out // the valid position function validPosition($arr, $N, $K) { $count = 0; $sum = 0; // find sum of all the elements for ($i = 0; $i < $N; $i++) { $sum += $arr[$i]; } // adding K to the element and check // whether it is greater than sum of // all other elements for ($i = 0; $i < $N; $i++) { if (($arr[$i] + $K) > ($sum - $arr[$i])) $count++; } return $count; } // Driver code $arr = array( 2, 1, 6, 7 ); $K = 4; $N = count($arr) ; echo validPosition($arr, $N, $K); // This code is contributed by AnkitRai01?> |
Javascript
<script>// Javascript program to implement above approach// Function that will find out// the valid positionfunction validPosition(arr, N, K){ var count = 0, sum = 0; // find sum of all the elements for (var i = 0; i < N; i++) { sum += arr[i]; } // adding K to the element and check // whether it is greater than sum of // all other elements for (var i = 0; i < N; i++) { if ((arr[i] + K) > (sum - arr[i])) count++; } return count;}// Driver codevar arr = [ 2, 1, 6, 7 ], K = 4;var N = arr.length;document.write( validPosition(arr, N, K));</script> |
Output:
1
Time Complexity : O(N)
Auxiliary Space : O(1)
