Given an array A[]. The task is to count the number of subsequences such that concatenation of binary representation of the numbers represents palindrome.
Examples:
Input: A[] = {1, 2, 3}
Output: 4
Explanation: Binary representation of all elements are {1, 10, 11}
here the concatenation of {1, 3} => 111 makes palindrome
similarly, concatenation of {1, 2, 3} => 11011 makes palindrome, and
element {1} and {3} already have a palindromic binary form
Hence, total 4 subsequences are possible whose binary concatenation makes palindromeInput: A[ ] = {4, 9, 3, 15, 23}
Output: 6
Approach: The problem can be solved by checking each subsequence for palindrome after converting the given array into the binary representation of each element.
Follow the steps to solve the problem:
- Firstly, replace all the integers of the array into their binary representation and store it into a vector of string.
- Now, find all the subsequence of the vector of string:
- Check, if the subsequence is a palindrome or not.
- If true, then increment the count.
- Lastly, print the count.
Below is the implementation of the above approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// Function to convert array element into// their binary representationvector<string> convert(vector<int> arr, int n){ vector<string> v; int i, x; for (i = 0; i < n; i++) { x = arr[i]; string s; // Convert into binary one by one while (x) { int r = x % 2; s += to_string(r); x /= 2; } // Reverse the string and store // into vector v reverse(s.begin(), s.end()); v.push_back(s); } return v;}// Function to check palindromebool palindrome(string a, int i, int j){ while (i < j) { // If the integer at i is // not equal to j // then return false if (a[i] != a[j]) return false; i++; j--; } // All a[i] is equal to a[j] // then return true return true;}// Function to count palindromic subsequencesvoid countSubsequences(vector<string> arr, int i, string s, int& count){ // Check the condition of palindrome // if it is the leaf of recursion tree if (i == arr.size()) { int l = s.length(); // Check for palindrome and // increment count if (l > 0 && palindrome(s, 0, l - 1)) { count++; } } else { // Subsequence without including // the element at current index countSubsequences(arr, i + 1, s, count); // Concatenate string s += (arr[i]); // Subsequence including the element // at current index countSubsequences(arr, i + 1, s, count); } return;}// Function to find all the subsequencesint solve(vector<int>& arr){ int count = 0, i = 0; vector<string> v = convert(arr, arr.size()); // Recursive function call countSubsequences(v, i, "", count); return count;}// Driver codeint main(){ vector<int> arr = { 4, 9, 3, 15, 23 }; // First replace all the array element // to their binary form int count = solve(arr); cout << count; return 0;} |
Java
// Java program for the above approachimport java.io.*; import java.util.*; class GFG{ static int count = 0; static String reverse(String str) { char[] chars = str.toCharArray(); for (int i = 0, j = str.length() - 1; i < j; i++, j--) { char c = chars[i]; chars[i] = chars[j]; chars[j] = c; } return new String(chars); } // Function to convert array element into // their binary representation static ArrayList convert(int[] arr, int n) { ArrayList<String> v = new ArrayList<String>(); int i = 0, x = 0; for (i = 0; i < n; i++) { x = arr[i]; String s = ""; // Convert into binary one by one while (x > 0) { int r = x % 2; s += Integer.toString(r); x /= 2; } // Reverse the String and store // into vector v s = reverse(s); v.add(s); } return v; } // Function to check palindrome static boolean palindrome(String a, int i, int j) { while (i < j) { // If the integer at i is // not equal to j // then return false if (a.charAt(i) != a.charAt(j)) { return false; } i++; j--; } // All a[i] is equal to a[j] // then return true return true; } // Function to count palindromic subsequences static void countSubsequences(ArrayList<String> arr, int i, String s) { // Check the condition of palindrome // if it is the leaf of recursion tree if (i == arr.size()) { int l = s.length(); // Check for palindrome and // increment count if (l > 0 && palindrome(s, 0, l - 1) == true) { count++; } } else { // Subsequence without including // the element at current index countSubsequences(arr, i + 1, s); // Concatenate String s += (arr.get(i)); // Subsequence including the element // at current index countSubsequences(arr, i + 1, s); } return; } // Function to find all the subsequences static int solve(int[] arr) { int i = 0; ArrayList<String> v = convert(arr, arr.length); // Recursive function call countSubsequences(v, i, ""); return count; } // Driver Code public static void main(String args[]) { int[] arr = { 4, 9, 3, 15, 23 }; // First replace all the array element // to their binary form int c = solve(arr); System.out.print(c); }}// This code is contributed by sanjoy_62. |
Python3
# Python3 code for the above approach# Taking count as a global variablecount = 0# Function to convert array element into# their binary representationdef convert(arr, n): v = [] for i in range(n): x = arr[i] s = "" # Convert into binary one by one while(x > 0): r = x % 2 s = s + str(r) x = x // 2 # Reverse the string and store # into list v s = s[::-1] v.append(s) return v# Function to check palindromedef palindrome(a, i, j): while(i < j): # If the integer at i is # not equal to j # then return false if(a[i] != a[j]): return False i = i + 1 j = j - 1 # All a[i] is equal to a[j] # then return true return True # Function to count palindromic subsequencesdef countSubsequences(arr, i, s): global count # Check the condition of palindrome # if it is the leaf of recursion tree if(i == len(arr)): l = len(s) # Check for palindrome and # increment count if(l > 0 and palindrome(s, 0, l - 1)): count = count + 1 else: # Subsequence without including # the element at current index countSubsequences(arr, i + 1, s) # Concatenate string s = s + arr[i] # Subsequence including the element # at current index countSubsequences(arr, i + 1, s) returndef solve(arr): i = 0 v = convert(arr, len(arr)) # Recursive function call countSubsequences(v, i, "") return count # Driver codearr = [4, 9, 3, 15, 23]# First replace all the array element# to their binary formcount = solve(arr)print(count)# This code is contributed by Pushpesh Raj |
C#
// C# implementation of above approachusing System;using System.Collections;class GFG { static int count = 0; static string reverse(string str) { char[] chars = str.ToCharArray(); for (int i = 0, j = str.Length - 1; i < j; i++, j--) { char c = chars[i]; chars[i] = chars[j]; chars[j] = c; } return new string(chars); } // Function to convert array element into // their binary representation static ArrayList convert(int[] arr, int n) { ArrayList v = new ArrayList(); int i = 0, x = 0; for (i = 0; i < n; i++) { x = arr[i]; string s = ""; // Convert into binary one by one while (x > 0) { int r = x % 2; s += r.ToString(); x /= 2; } // Reverse the string and store // into vector v s = reverse(s); v.Add(s); } return v; } // Function to check palindrome static bool palindrome(string a, int i, int j) { while (i < j) { // If the integer at i is // not equal to j // then return false if (a[i] != a[j]) { return false; } i++; j--; } // All a[i] is equal to a[j] // then return true return true; } // Function to count palindromic subsequences static void countSubsequences(ArrayList arr, int i, string s) { // Check the condition of palindrome // if it is the leaf of recursion tree if (i == arr.Count) { int l = s.Length; // Check for palindrome and // increment count if (l > 0 && palindrome(s, 0, l - 1) == true) { count++; } } else { // Subsequence without including // the element at current index countSubsequences(arr, i + 1, s); // Concatenate string s += (arr[i]); // Subsequence including the element // at current index countSubsequences(arr, i + 1, s); } return; } // Function to find all the subsequences static int solve(int[] arr) { int i = 0; ArrayList v = convert(arr, arr.Length); // Recursive function call countSubsequences(v, i, ""); return count; } // Driver code public static void Main() { int[] arr = { 4, 9, 3, 15, 23 }; // First replace all the array element // to their binary form int c = solve(arr); Console.Write(c); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// Taking count as a global variablelet count = 0// Function to convert array element into// their binary representationfunction convert(arr, n){ let v = [] for(let i = 0; i < n; i++){ let x = arr[i] let s = "" // Convert into binary one by one while(x > 0){ let r = x % 2 s += r.toString() x = Math.floor(x / 2) } // Reverse the string and store // into list v s = s.split("").reverse().join("") v.push(s) } return v}// Function to check palindromefunction palindrome(a, i, j){ while(i < j){ // If the integer at i is // not equal to j // then return false if(a[i] != a[j]) return false i = i + 1 j = j - 1 } // All a[i] is equal to a[j] // then return true return true} // Function to count palindromic subsequencesfunction countSubsequences(arr, i, s){ // Check the condition of palindrome // if it is the leaf of recursion tree if(i == arr.length){ let l = s.length // Check for palindrome and // increment count if(l > 0 && palindrome(s, 0, l - 1)) count = count + 1 } else { // Subsequence without including // the element at current index countSubsequences(arr, i + 1, s) // Concatenate string s = s + arr[i] // Subsequence including the element // at current index countSubsequences(arr, i + 1, s) } return}function solve(arr){ let i = 0 let v = convert(arr, arr.length) // Recursive function call countSubsequences(v, i, "") return count} // Driver codelet arr = [4, 9, 3, 15, 23]// First replace all the array element// to their binary formcount = solve(arr)document.write(count,"</br>")// This code is contributed by shinjanpatra</script> |
Output
6
Time Complexity: O(2N * N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
