Related Articles
Find two non-intersecting subarrays having equal sum of all elements raised to the power of 2
• Last Updated : 12 Apr, 2021

Given an array arr[] of positive integers of size N, the task is to check if there exists two non-intersecting subarrays in arr[] such that sum of all possible 2(subarr[i]) and the sum of all possible 2(subarr2[j]) are equal.

Examples:

Input: arr[] = {4, 3, 0, 1, 2, 0}
Output: YES
Explanation: Expressing every array element in the form of 2arr[i], the array is modified to { 16, 8, 1, 2, 4, 1 }.
Therefore, two valid subarrays are { 16 } and { 8, 1, 2, 4, 1 } whose sum are equal.

Input: arr[]={ 3, 4 }
Output: NO

Approach: Since binary representation of all powers of 2 is unique, two sch subarrays can only be obtained if any repeating element is present in that array. Otherwise, it is not possible.

Follow the steps below to solve the problem:

Below is the implementation of the above approach:

## C++

 `// C++ program for the above approach` `#include ``using` `namespace` `std;` `// Function to check if two non-intersecting``// subarrays with equal sum exists or not``void` `findSubarrays(``int` `arr[], ``int` `N)``{``    ``// Sort the given array``    ``sort(arr, arr + N);``    ``int` `i = 0;` `    ``// Traverse the array``    ``for` `(i = 0; i < N - 1; i++) {` `        ``// Check for duplicate elements``        ``if` `(arr[i] == arr[i + 1]) {` `            ``cout << ``"YES"` `<< endl;``            ``return``;``        ``}``    ``}` `    ``// If no duplicate element is``    ``// present in the array``    ``cout << ``"NO"` `<< endl;``}` `// Driver Code``int` `main()``{``    ``// Given array``    ``int` `arr[] = { 4, 3, 0, 1, 2, 0 };` `    ``// Size of array``    ``int` `N = ``sizeof``(arr) / ``sizeof``(arr);` `    ``findSubarrays(arr, N);` `    ``return` `0;``}`

## Java

 `// Java program for the above approach``import` `java.util.*;`` ` `class` `GFG{``     ` `// Function to check if two non-intersecting``// subarrays with equal sum exists or not``static` `void` `findSubarrays(``int` `arr[], ``int` `N)``{``    ` `    ``// Sort the given array``    ``Arrays.sort(arr);``    ``int` `i = ``0``;`` ` `    ``// Traverse the array``    ``for``(i = ``0``; i < N - ``1``; i++)``    ``{``        ` `        ``// Check for duplicate elements``        ``if` `(arr[i] == arr[i + ``1``])``        ``{``            ``System.out.println(``"YES"``);``            ``return``;``        ``}``    ``}`` ` `    ``// If no duplicate element is``    ``// present in the array``    ``System.out.println(``"NO"``);``}`` ` `// Driver code``public` `static` `void` `main(String[] args)``{``    ` `    ``// Given array``    ``int``[] arr = { ``4``, ``3``, ``0``, ``1``, ``2``, ``0` `};`` ` `    ``// Size of array``    ``int` `N = arr.length;`` ` `    ``findSubarrays(arr, N);``}``}` `// This code is contributed by susmitakundugoaldanga`

## Python3

 `# Python program for the above approach` `# Function to check if two non-intersecting``# subarrays with equal sum exists or not``def` `findSubarrays(arr, N):``  ` `    ``# Sort the given array``    ``arr.sort();``    ``i ``=` `0``;` `    ``# Traverse the array``    ``for` `i ``in` `range``(N ``-` `1``):` `        ``# Check for duplicate elements``        ``if` `(arr[i] ``=``=` `arr[i ``+` `1``]):``            ``print``(``"YES"``);``            ``return``;` `    ``# If no duplicate element is``    ``# present in the array``    ``print``(``"NO"``);` `# Driver code``if` `__name__ ``=``=` `'__main__'``:``  ` `    ``# Given array``    ``arr ``=` `[``4``, ``3``, ``0``, ``1``, ``2``, ``0``];` `    ``# Size of array``    ``N ``=` `len``(arr);` `    ``findSubarrays(arr, N);` `# This code is contributed by 29AjayKumar`

## C#

 `// C# program for the above approach``using` `System;``  ` `class` `GFG{``      ` `// Function to check if two non-intersecting``// subarrays with equal sum exists or not``static` `void` `findSubarrays(``int``[] arr, ``int` `N)``{``    ` `    ``// Sort the given array``    ``Array.Sort(arr);``    ``int` `i = 0;``  ` `    ``// Traverse the array``    ``for``(i = 0; i < N - 1; i++)``    ``{``        ` `        ``// Check for duplicate elements``        ``if` `(arr[i] == arr[i + 1])``        ``{``            ``Console.WriteLine(``"YES"``);``            ``return``;``        ``}``    ``}``  ` `    ``// If no duplicate element is``    ``// present in the array``    ``Console.WriteLine(``"NO"``);``}``  ` `// Driver code``public` `static` `void` `Main()``{``    ` `    ``// Given array``    ``int``[] arr = { 4, 3, 0, 1, 2, 0 };``  ` `    ``// Size of array``    ``int` `N = arr.Length;``  ` `    ``findSubarrays(arr, N);``}``}` `// This code is contributed by sanjoy_62`

## Javascript

 ``
Output:
`YES`

Time Complexity: O(NLogN)
Auxiliary Space: O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

My Personal Notes arrow_drop_up
{"ft_lang_label":"__label__en","ft_lang_prob":0.5097666,"math_prob":0.9534762,"size":4523,"snap":"2021-04-2021-17","text_gpt3_token_len":1408,"char_repetition_ratio":0.13808365,"word_repetition_ratio":0.3642534,"special_character_ratio":0.3431351,"punctuation_ratio":0.17165005,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9985875,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-04-14T21:10:01Z\",\"WARC-Record-ID\":\"<urn:uuid:08634951-ca33-4e50-95fa-1f73e6216181>\",\"Content-Length\":\"122562\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:0b242df8-6645-41c8-8a08-af4158ce6d67>\",\"WARC-Concurrent-To\":\"<urn:uuid:89b2782f-cbd8-41b9-9a59-271c5c33d246>\",\"WARC-IP-Address\":\"204.237.142.139\",\"WARC-Target-URI\":\"https://www.geeksforgeeks.org/find-two-non-intersecting-subarrays-having-equal-sum-of-all-elements-raised-to-the-power-of-2/\",\"WARC-Payload-Digest\":\"sha1:B25IFQ6UKFDCRFZ65G47WJOQIJ35CSMH\",\"WARC-Block-Digest\":\"sha1:EA2BN6G7F7URYPTALF4EWUBJTXQXIIVW\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-17/CC-MAIN-2021-17_segments_1618038078021.18_warc_CC-MAIN-20210414185709-20210414215709-00430.warc.gz\"}"}