Check if array can be divided into two sub-arrays such that their absolute difference is K
Given an array arr[] and an integer K, the task is to find whether the array can be divided into two sub-arrays such that the absolute difference of the sum of the elements of both the sub-arrays is K.
Examples:
Input: arr[] = {2, 4, 5, 1}, K = 0
Output: Yes
{2, 4} and {5, 1} are the two possible sub-arrays.
|(2 + 4) – (5 + 1)| = |6 – 6| = 0Input: arr[] = {2, 4, 1, 5}, K = 2
Output: No
Approach:
- Assume there exists an answer, let the sum of elements of the sub-array (with smaller sum) is S.
- Sum of the elements of the second array will be S + K.
- And, S + S + K must be equal to sum of all the elements of the array say totalSum = 2 *S + K.
- S = (totalSum – K) / 2
- Now, traverse the array till we achieve a sum of S starting from the first element and if its not possible then print No.
- Else print Yes.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Function that return true if it is possible // to divide the array into sub-arrays // that satisfy the given condition bool solve( int array[], int size, int k) { // To store the sum of all the elements // of the array int totalSum = 0; for ( int i = 0; i < size; i++) totalSum += array[i]; // Sum of any sub-array cannot be // a floating point value if ((totalSum - k) % 2 == 1) return false ; // Required sub-array sum int S = (totalSum - k) / 2; int sum = 0; for ( int i = 0; i < size; i++) { sum += array[i]; if (sum == S) return true ; } return false ; } // Driver Code int main() { int array[] = { 2, 4, 1, 5 }; int k = 2; int size = sizeof (array) / sizeof (array[0]); if (solve(array, size, k)) cout << "Yes" << endl; else cout << "No" << endl; } |
Java
/*package whatever //do not write package name here */ import java.io.*; class GFG { // Function that return true if it is possible // to divide the array into sub-arrays // that satisfy the given condition static boolean solve( int array[], int size, int k) { // To store the sum of all the elements // of the array int totalSum = 0 ; for ( int i = 0 ; i < size; i++) totalSum += array[i]; // Sum of any sub-array cannot be // a floating point value if ((totalSum - k) % 2 == 1 ) return false ; // Required sub-array sum int S = (totalSum - k) / 2 ; int sum = 0 ; for ( int i = 0 ; i < size; i++) { sum += array[i]; if (sum == S) return true ; } return false ; } // Driver Code public static void main (String[] args) { int array[] = { 2 , 4 , 1 , 5 }; int k = 2 ; int size = array.length; if (solve(array, size, k)) System.out.println ( "Yes" ); else System.out.println ( "No" ); } } // This Code is contributed by akt_mit |
Python3
# Function that return true if it is possible # to divide the array into sub-arrays # that satisfy the given condition def solve(array,size,k): # To store the sum of all the elements # of the array totalSum = 0 for i in range ( 0 ,size): totalSum + = array[i] # Sum of any sub-array cannot be # a floating point value if ((totalSum - k) % 2 = = 1 ): return False # Required sub-array sum S = (totalSum - k) / 2 sum = 0 ; for i in range ( 0 ,size): sum + = array[i] if ( sum = = S): return True return False # Driver Code array = [ 2 , 4 , 1 , 5 ] k = 2 n = 4 if (solve(array, n, k)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by iAyushRaj. |
C#
using System; class GFG { // Function that return true if it is possible // to divide the array into sub-arrays // that satisfy the given condition public static bool solve( int [] array, int size, int k) { // To store the sum of all the elements // of the array int totalSum = 0; for ( int i = 0; i < size; i++) totalSum += array[i]; // Sum of any sub-array cannot be // a floating point value if ((totalSum - k) % 2 == 1) return false ; // Required sub-array sum int S = (totalSum - k) / 2; int sum = 0; for ( int i = 0; i < size; i++) { sum += array[i]; if (sum == S) return true ; } return false ; } // Driver Code public static void Main() { int [] array = { 2, 4, 1, 5 }; int k = 2; int size = 4; if (solve(array, size, k)) Console.Write( "Yes" ); else Console.Write( "No" ); } } // This code is contributed by iAyushRaj. |
PHP
<?php // Function that return true if it is possible // to divide the array into sub-arrays // that satisfy the given condition function solve( $array , $size , $k ) { // To store the sum of all the elements // of the array $totalSum = 0; for ( $i = 0; $i < $size ; $i ++) $totalSum += $array [ $i ]; // Sum of any sub-array cannot be // a floating point value if (( $totalSum - $k ) % 2 == 1) return false; // Required sub-array sum $S = ( $totalSum - $k ) / 2; $sum = 0; for ( $i = 0; $i < $size ; $i ++) { $sum += $array [ $i ]; if ( $sum == $S ) return true; } return false; } // Driver Code $array = array ( 2, 4, 1, 5 ); $k = 2; $size = sizeof( $array ); if (solve( $array , $size , $k )) echo "Yes" ; else echo "No" ; // This code is contributed by iAyushRaj. ?> |
Javascript
<script> // Javascript program to illustrate // the above problem // Function that return true if it is possible // to divide the array into sub-arrays // that satisfy the given condition function solve(array, size, k) { // To store the sum of all the elements // of the array let totalSum = 0; for (let i = 0; i < size; i++) totalSum += array[i]; // Sum of any sub-array cannot be // a floating point value if ((totalSum - k) % 2 == 1) return false ; // Required sub-array sum let S = (totalSum - k) / 2; let sum = 0; for (let i = 0; i < size; i++) { sum += array[i]; if (sum == S) return true ; } return false ; } // Driver Code let array = [ 2, 4, 1, 5 ]; let k = 2; let size = array.length; if (solve(array, size, k)) document.write( "Yes" ); else document.write ( "No" ); </script> |
Output
No
Complexity Analysis:
- Time Complexity: O(n) where n is the size of the array.
- Auxiliary Space: O(1)
Contact Us