Quadruples with unequal sum of first two and last two elements
Given an array arr[] of length N (N >= 4). The task is to check whether there exists a quadruple such that the sum of first two elements is not equal to sum of last two elements. In other words, we need to check whether there exist four integers (0 <= i < j < k < l < N) such that (arr[i] + arr[j] != arr[k] + arr[l]).
Examples:
Input: N = 4, arr[] = {1, 2, 3, 4}
Output: YES
Explanation: The indices (i, j, k, l) are (0, 1, 2, 3) respectively. At these indices the condition (arr[0] + arr[1] != arr[2] + arr[3]) is satisfied as ((1 + 2) != (3 + 4)). Therefore, 4 valid indices are present in arr[].Input: N = 5, arr[] = {2, 2, 2, 2, 2}
Output: NO
Explanation: It can be verified that no combination of 4 indices satisfies the condition (arr[0] + arr[1] != arr[2] + arr[3]).
Approach: To solve the problem, follow the below idea:
The problem is observation based. The main idea is, if at least one element in arr[] is different than the rest then we will always be able to find 4 indices such that arr[i] + arr[j] != arr[k] + arr[l]. At any instance we can have 2 cases mentioned below:
- When N is equal to 4:
- In such case we just have to check the condition (arr[0] + arr[1] != arr[2] + arr[3]).
- When N is greater than 4:
- In such cases the 4 indices will not satisfy the given condition only and only if all elements are same. This can be proved by the following mathematical expression.
Consider that, arr[] = {A1, A2, A3, A4, A5} having N = 5. Then, let us try to prove (arr[0] + arr[1] == arr[2] + arr[3]) (Please note that, it is opposite of what is asked in problem statement)
- Proof that (A1 = A2):
- Equation (i): (A1 + A3) = (A4 + A5), whose indices follows the condition (1 <= i < j < k < l <= N).
- Equation (ii): (A2 + A3) = (A4 + A5), whose indices follows the condition (1 <= i < j < k < l <= N).
- As RHS (Right Hand Side) is same, A1 = A2.
- Proof that (A3 = A5):
- Equation (i): (A1 + A2) = (A4 + A5), whose indices follows the condition (1 <= i < j < k < l <= N).
- Equation (ii): (A1 + A2) = (A3 + A4), whose indices follows the condition (1 <= i < j < k < l <= N).
- As LHS (Left Hand Side) is same, A3 = A5.
- Proof that (A1 = A3):
- Equation (i): (A1 + A2) = (A4 + A5), whose indices follows the condition (1 <= i < j < k < l <= N).
- Equation (ii): (A2 + A3) = (A4 + A5), whose indices follows the condition (1 <= i < j < k < l <= N).
- As RHS is same, A1 = A3. We have proven that (A1 = A2), (A3 = A5) and (A1 = A3). Which gives (A1 = A2 = A3 = A5).
- Proof that (A4 = A2):
- Equation (i): (A1 + A2) = (A4 + A5), whose indices follows the condition (1 <= i < j < k < l <= N). As it has proven that A1 = A5 above. So, after replacing A1 with A5 in LHS, we get (A5 + A2) = (A4 + A5). Therefore, A2 = A4 and (A1 = A2 = A3 = A4 = A5).
Now, it has proved that, for any arr[] having length greater than 4, the condition (arr[0] + arr[1] == arr[2] + arr[3]) will be true only and only if (A1 = A2 = A3 = A4 = A5). So, the opposite condition (arr[0] + arr[1] != arr[2] + arr[3]) will be true only when there will be at least one different element.
Step-by-step algorithm:
- If (N == 4)
- Check for the asked condition manually and output the answer according to that.
- If (N > 4)
- If all the elements are same, then output NO else YES.
Below is the implementation of the approach:
C++
// code by flutterflow #include <iostream> // Function to check if there exist 4 indices satisfying the condition void CheckIndices( int N, int X[]) { // If length of X[] is 4 if (N == 4) { // Checking for the desired condition manually if (X[0] + X[1] == X[2] + X[3]) std::cout << "NO" << std::endl; else std::cout << "YES" << std::endl; } // If length of X[] is greater than 4 else { // First element of X[] int first_element = X[0]; // Boolean flag bool flag = true ; // Checking that all elements are equal to the first element or not // Formally, all elements are equal or not for ( int i = 1; i < N; i++) { // If at least one different element is there, // then mark flag as false and break the loop if (X[i] != first_element) { flag = false ; break ; } } // Printing the result based on the Boolean flag std::cout << (flag ? "NO" : "YES" ) << std::endl; } } // Driver Function int main() { // Inputs int N = 4; int X[] = {3, 6, 7, 4}; // Function call CheckIndices(N, X); return 0; } |
Java
// Java code to implement the approach import java.util.*; // Driver Class public class Main { // Driver Function public static void main(String[] args) { // Inputs int N = 4 ; int [] X = { 3 , 6 , 7 , 4 }; // Function_call CheckIndices(N, X); } // Method to check if there exists 4 indices satisfied // the asked condition public static void CheckIndices( int N, int [] X) { // If length of X[] is 4 if (N == 4 ) { // Checking for the desired condition manually if (X[ 0 ] + X[ 1 ] == X[ 2 ] + X[ 3 ]) System.out.println("NO"); else System.out.println("YES"); } // If length of X[] is greater than 4 else { // First element of X[] int first_element = X[ 0 ]; // Boolean flag boolean flag = true ; // Checking that all elements are equal to first // element or not Formally, all elements are // equal or not for ( int i = 1 ; i < N; i++) { // If at least one different element is // there Then mark flag as false and break // the loop if (X[i] != first_element) { flag = false ; break ; } } // Printing the result based on the Boolean flag System.out.println(flag ? "NO" : "YES"); } } } |
Python3
# code by flutterfly def check_indices(N, X): # If length of X[] is 4 if N = = 4 : # Checking for the desired condition manually if X[ 0 ] + X[ 1 ] = = X[ 2 ] + X[ 3 ]: print ( "NO" ) else : print ( "YES" ) # If length of X[] is greater than 4 else : # First element of X[] first_element = X[ 0 ] # Boolean flag flag = True # Checking that all elements are equal to the first element or not # Formally, all elements are equal or not for i in range ( 1 , N): # If at least one different element is there, # then mark flag as false and break the loop if X[i] ! = first_element: flag = False break # Printing the result based on the Boolean flag print ( "NO" if flag else "YES" ) # Driver Function def main(): # Inputs N = 4 X = [ 3 , 6 , 7 , 4 ] # Function call check_indices(N, X) if __name__ = = "__main__" : main() |
C#
//code by flutterfly using System; class Program { // Function to check if there exist 4 indices satisfying the condition static void CheckIndices( int N, int [] X) { // If length of X[] is 4 if (N == 4) { // Checking for the desired condition manually if (X[0] + X[1] == X[2] + X[3]) Console.WriteLine( "NO" ); else Console.WriteLine( "YES" ); } // If length of X[] is greater than 4 else { // First element of X[] int first_element = X[0]; // Boolean flag bool flag = true ; // Checking that all elements are equal to the first element or not // Formally, all elements are equal or not for ( int i = 1; i < N; i++) { // If at least one different element is there, // then mark flag as false and break the loop if (X[i] != first_element) { flag = false ; break ; } } // Printing the result based on the Boolean flag Console.WriteLine(flag ? "NO" : "YES" ); } } // Driver Function static void Main() { // Inputs int N = 4; int [] X = { 3, 6, 7, 4 }; // Function call CheckIndices(N, X); } } |
Javascript
function checkIndices(N, X) { // If length of X[] is 4 if (N === 4) { // Checking for the desired condition manually if (X[0] + X[1] === X[2] + X[3]) { console.log( "NO" ); } else { console.log( "YES" ); } } // If length of X[] is greater than 4 else { // First element of X[] const firstElement = X[0]; // Boolean flag let flag = true ; // Checking that all elements are equal to the first element or not // Formally, all elements are equal or not for (let i = 1; i < N; i++) { // If at least one different element is there, // then mark flag as false and break the loop if (X[i] !== firstElement) { flag = false ; break ; } } // Printing the result based on the Boolean flag console.log(flag ? "NO" : "YES" ); } } // Driver Function function main() { // Inputs const N = 4; const X = [3, 6, 7, 4]; // Function call checkIndices(N, X); } // Run the main function main(); |
YES
Time Complexity: O(N), where N is the size of input array arr[].
Auxiliary Space: O(1)