Given an array arr[] consisting of N integers, the task is to check if the sum of all possible values of (arr[i] / j) for all pairs (i, j) such that 0 < i ? j < (N – 1) is 0 or not. If found to be true, then print “Yes”. Otherwise, print “No”.
Examples:
Input: arr[] = {1, -1, 3, -2, -1}
Output: Yes
Explanation:
For all possible pairs (i, j), such that 0 < i <= j < (N – 1), required sum = 1/1 + -1/2 + 3/3 + -2/4 + -1/5 + -1/2 + 3/3 + -2/4 + -1/5 + 3/3 + -2/4 + -1/5 + -2/ 4 + -1/5 + -1/5 = 0.Input: arr[] = {1, 2, 3, 4, 5}
Output: No
Approach: The given problem can be solved based on the following observations:
- For every possible value of i over the range [0, N – 1] and for every possible values of j following are the expressions:
- j = 1:
- j = 2:
- j = 3:
3rd line and so on…
- j = 1:
- Therefore, the sum of all the above expression is given by:
3rd line and so on…=>
=>
From the above observations, if the sum of the array is 0, then print Yes. Otherwise, print No.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if sum of all// values of (arr[i]/j) for all// 0 < i <= j < (N - 1) is 0 or notvoid check(int arr[], int N){ // Stores the required sum int sum = 0; // Traverse the array for (int i = 0; i < N; i++) sum += arr[i]; // If the sum is equal to 0 if (sum == 0) cout << "Yes"; // Otherwise else cout << "No";}// Driver Codeint main(){ int arr[] = { 1, -1, 3, -2, -1 }; int N = sizeof(arr) / sizeof(arr[0]); check(arr, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{// Function to check if sum of all// values of (arr[i]/j) for all// 0 < i <= j < (N - 1) is 0 or notstatic void check(int arr[], int N){ // Stores the required sum int sum = 0; // Traverse the array for(int i = 0; i < N; i++) sum += arr[i]; // If the sum is equal to 0 if (sum == 0) System.out.println("Yes"); // Otherwise else System.out.println("No");}// Driver Codepublic static void main(String[] args){ int arr[] = { 1, -1, 3, -2, -1 }; int N = arr.length; check(arr, N);}}// This code is contributed by Kingash |
Python3
# Python3 program for the above approach# Function to check if sum of all# values of (arr[i]/j) for all# 0 < i <= j < (N - 1) is 0 or notdef check(arr, N): # Stores the required sum sum = 0 # Traverse the array for i in range(N): sum += arr[i] # If the sum is equal to 0 if (sum == 0): print("Yes") # Otherwise else: print("No")# Driver Codeif __name__ == '__main__': arr = [ 1, -1, 3, -2, -1 ] N = len(arr) check(arr, N)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG { // Function to check if sum of all // values of (arr[i]/j) for all // 0 < i <= j < (N - 1) is 0 or not static void check(int[] arr, int N) { // Stores the required sum int sum = 0; // Traverse the array for (int i = 0; i < N; i++) sum += arr[i]; // If the sum is equal to 0 if (sum == 0) Console.WriteLine("Yes"); // Otherwise else Console.WriteLine("No"); } // Driver Code public static void Main(string[] args) { int[] arr = { 1, -1, 3, -2, -1 }; int N = arr.Length; check(arr, N); }}// This code is contributed by ukasp. |
Javascript
<script>// javascript program for the above approach // Function to check if sum of all // values of (arr[i]/j) for all // 0 < i <= j < (N - 1) is 0 or not function check(arr , N) { // Stores the required sum var sum = 0; // Traverse the array for (i = 0; i < N; i++) sum += arr[i]; // If the sum is equal to 0 if (sum == 0) document.write("Yes"); // Otherwise else document.write("No"); } // Driver Code var arr = [ 1, -1, 3, -2, -1 ]; var N = arr.length; check(arr, N);// This code contributed by umadevi9616</script> |
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
