Subsets of size K with product equal to difference of two perfect squares
Given a distinct integers array arr[] of size N and an integer K, the task is to count the number of subsets of size K of array whose product of elements can be represented as a2 – b2. Examples:
Input: arr[] = {1, 2, 3} K = 2 Output: 2 Explanation: All possible subsets of length 2 with their products are given below: {1, 2} = 2 {2, 3} = 6 {1, 3} = 3 Since, only 3 can be expressed as (22 – 12, therefore only one such subset exists. Input: arr[] = {2, 5, 6} K = 2 Output: 2 Explanation: All possible contiguous sub-sequences with their products given below: {2, 5} = 10 {2, 6} = 12 {5, 6} = 30 Since, only 12 can be expressed as (42 – 22), only one such subset exists.
Approach:
- Generate all subsets of size K.
- Calculate the products of all subsets.
- A number can be represented as the difference of square of two numbers only if it is odd or divisible by 4.
- Hence, count all subsets with product that satisfies this condition.
Below is the implementation of the above approach:
C++
// C++ Code #include <bits/stdc++.h> using namespace std; vector<vector< int > > combs; void combinationUtil( int arr[], int data[], int start, int end, int index, int r) { // Current combination is ready to be printed, print it if (index == r) { vector< int > comb; for ( int j = 0; j < r; j++) comb.push_back(data[j]); combs.push_back(comb); return ; } // replace index with all possible elements. The // condition "end-i+1 >= r-index" makes sure that // including one element at index will make a // combination with remaining elements at remaining // positions for ( int i = start; i <= end && end - i + 1 >= r - index; i++) { data[index] = arr[i]; combinationUtil(arr, data, i + 1, end, index + 1, r); } } // Count of required sub-sequences int count_seq( int arr[], int n, int k) { // ans is Count variable int ans = 0; for (vector< int > seq : combs) { // product of seq int pro = 1; for ( int ele : seq) pro *= ele; // checking form of a2-b2 if ((pro % 4) != 2) ans += 1; } return ans; } // Driver Code int main() { int arr[] = { 2, 5, 6 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 2; int data[k]; combinationUtil(arr, data, 0, n - 1, 0, k); cout << count_seq(arr, n, k) << endl; return 0; } // This code is contributed by akashish__ |
Java
/*package whatever //do not write package name here */ import java.util.*; class GFG { static List<List<Integer>> combs = new ArrayList<>(); static void combinationUtil( int arr[], int data[], int start, int end, int index, int r) { // Current combination is ready to be printed, print it if (index == r) { List<Integer> comb = new ArrayList<>(); for ( int j= 0 ; j<r; j++) comb.add(data[j]); combs.add(comb); return ; } // replace index with all possible elements. The condition // "end-i+1 >= r-index" makes sure that including one element // at index will make a combination with remaining elements // at remaining positions for ( int i=start; i<=end && end-i+ 1 >= r-index; i++) { data[index] = arr[i]; combinationUtil(arr, data, i+ 1 , end, index+ 1 , r); } } // Count of required sub-sequences static int count_seq( int []arr, int n, int k){ // ans is Count variable int ans = 0 ; for (List<Integer> seq:combs){ // product of seq int pro = 1 ; for ( int ele:seq) pro *= ele; // checking form of a2-b2 if ((pro % 4 ) != 2 ) ans += 1 ; } return ans; } public static void main (String[] args) { int []arr = { 2 , 5 , 6 }; int n = arr.length; int k = 2 ; combinationUtil(arr, new int [k], 0 , n- 1 , 0 , k); System.out.println(count_seq(arr, n, k)); } } // This code is contributed by aadityaburujwale. |
Python3
# Python3 implementation of the approach import itertools # Function to return the # Count of required sub-sequences def count_seq(arr, n, k): # ans is Count variable ans = 0 for seq in itertools.combinations(arr, k): # product of seq pro = 1 for ele in seq: pro * = ele # checking form of a2-b2 if ((pro % 4 ) ! = 2 ): ans + = 1 return ans # Driver code if __name__ = = "__main__" : arr = [ 2 , 5 , 6 ] n = len (arr) k = 2 print (count_seq(arr, n, k)) |
C#
using System; using System.Collections.Generic; public class GFG { static List<List< int > > combs = new List<List< int > >(); static void combinationUtil( int [] arr, int [] data, int start, int end, int index, int r) { // Current combination is ready to be printed, print // it if (index == r) { List< int > comb = new List< int >(); for ( int j = 0; j < r; j++) comb.Add(data[j]); combs.Add(comb); return ; } // replace index with all possible elements. The // condition "end-i+1 >= r-index" makes sure that // including one element at index will make a // combination with remaining elements at remaining // positions for ( int i = start; i <= end && end - i + 1 >= r - index; i++) { data[index] = arr[i]; combinationUtil(arr, data, i + 1, end, index + 1, r); } } // Count of required sub-sequences static int count_seq( int [] arr, int n, int k) { // ans is Count variable int ans = 0; foreach (List< int > seq in combs) { // product of seq int pro = 1; foreach ( int ele in seq) pro *= ele; // checking form of a2-b2 if ((pro % 4) != 2) ans += 1; } return ans; } static public void Main() { int [] arr = { 2, 5, 6 }; int n = arr.Length; int k = 2; combinationUtil(arr, new int [k], 0, n - 1, 0, k); Console.WriteLine(count_seq(arr, n, k)); } } // This code is contributed by akashish__ |
Javascript
// JavaScript Code const combs = []; function combinationUtil(arr, data, start, end, index, r) { // Current combination is ready to be printed, print it if (index == r) { let comb = []; for (let j = 0; j < r; j++) { comb.push(data[j]); } combs.push(comb); return ; } // replace index with all possible elements. The // condition "end-i+1 >= r-index" makes sure that // including one element at index will make a // combination with remaining elements at remaining // positions for (let i = start; i <= end && end - i + 1 >= r - index; i++) { data[index] = arr[i]; combinationUtil(arr, data, i + 1, end, index + 1, r); } } // Count of required sub-sequences function count_seq(arr, n, k) { // ans is Count variable let ans = 0; for (let seq of combs) { // product of seq let pro = 1; for (let ele of seq) { pro *= ele; } // checking form of a2-b2 if ((pro % 4) != 2) { ans += 1; } } return ans; } // Driver Code let arr = [2, 5, 6]; let n = arr.length; let k = 2; let data = new Array(k); combinationUtil(arr, data, 0, n - 1, 0, k); console.log(count_seq(arr, n, k)); // contributed by akashish__ |
Output:
1