Given an array arr[] of distinct elements -109 ? ai ? 109. The task is to find the largest sub-set from the given array such that the absolute difference between any two numbers in the sub-set is a positive power of two. If it is not possible to make such sub-set then print -1.
Examples:
Input: arr[] = {3, 4, 5, 6, 7}
Output: 3 5 7
|3 – 5| = 21, |5 – 7| = 21 and |3 – 7| = 22.Input: arr[] = {2, 5, 8}
Output: -1
Approach: Let’s prove that the size of the sub-set will not be > 3. Suppose a, b, c and d are four elements from a sub-set and a < b < c < d.
Let abs(a – b) = 2k and abs(b – c) = 2l then abs(a – c) = abs(a – b) + abs(b – c) = 2k + 2l = 2m. It means that k = l. Conditions must hold for the triple (b, c, d) too. Now it is easy to see that if abs(a – b) = abs(b – c) = abs(c – d) = 2k then abs(a – d) = abs(a – b) * 3 which is not a power of two. So the size of the sub-set will never be greater than 3.
- Let’s check if the answer is 3. Iterate over the given array for middle elements of the sub-set and for powers of two from 1 to 30 inclusively. Let xi be the middle element of the sub-set and j the current power of two. Then if there are elements xi-2j and xi+2j in the array then the answer is 3.
- Else check if the answer is 2. repeat the previous step but here one can get either left point xi-2j or xi+2j.
- If the answer is neither 2 nor 3 then print -1.
Below is the implementation of the above approach:
C++
// CPP program to find sub-set with// maximum possible size#include <bits/stdc++.h>using namespace std;// Function to find sub-set with// maximum possible sizevoid PowerOfTwo(vector<int> x, int n){ // Sort the given array sort(x.begin(), x.end()); // To store required sub-set vector<int> res; for (int i = 0; i < n; ++i) { // Iterate for all powers of two for (int j = 1; j < 31; ++j) { // Left number int lx = x[i] - (1 << j); // Right number int rx = x[i] + (1 << j); // Predefined binary search in c++ bool isl = binary_search(x.begin(), x.end(), lx); bool isr = binary_search(x.begin(), x.end(), rx); // If possible to get sub-set of size 3 if (isl && isr && int(res.size()) < 3) res = { lx, x[i], rx }; // If possible to get sub-set of size 2 if (isl && int(res.size()) < 2) res = { lx, x[i] }; // If possible to get sub-set of size 2 if (isr && int(res.size()) < 2) res = { x[i], rx }; } } // If not possible to get sub-set if (!res.size()) { cout << -1; return; } // Print the sub-set for (auto it : res) cout << it << " ";}// Driver Codeint main(){ vector<int> a = { 3, 4, 5, 6, 7 }; int n = a.size(); PowerOfTwo(a, n); return 0;} |
Java
// Java program to find sub-set with// maximum possible sizeimport java.util.*;class GFG{ // Function to find sub-set with// maximum possible sizestatic void PowerOfTwo(int []x, int n){ // Sort the given array Arrays.sort(x); // To store required sub-set ArrayList<Integer> res = new ArrayList<Integer>(); for (int i = 0; i < n; ++i) { // Iterate for all powers of two for (int j = 1; j < 31; ++j) { // Left number int lx = x[i] - (1 << j); // Right number int rx = x[i] + (1 << j); // Predefined binary search in Java boolean isl = Arrays.binarySearch(x,lx) < 0 ? false : true; boolean isr = Arrays.binarySearch(x,rx) < 0 ? false : true; // If possible to get sub-set of size 3 if (isl && isr && res.size() < 3) { res.clear(); res.add(lx); res.add(x[i]); res.add(rx); } // If possible to get sub-set of size 2 if (isl && res.size() < 2) { res.clear(); res.add(lx); res.add(x[i]); } // If possible to get sub-set of size 2 if (isr && res.size() < 2) { res.clear(); res.add(x[i]); res.add(rx); } } } // If not possible to get sub-set if (res.size() == 0) { System.out.println("-1"); return; } // Print the sub-set for (int i = 0; i < res.size(); i++) System.out.print(res.get(i) + " ");}// Driver Codepublic static void main (String[] args) { int[] a = {3, 4, 5, 6, 7}; int n = a.length; PowerOfTwo(a, n);}}// This code is Contributed by chandan_jnu |
Python3
# Python3 program to find sub-set with # maximum possible size # Function to find sub-set with # maximum possible size def PowerOfTwo(x, n) : # Sort the given array x.sort() # To store required sub-set res = [] for i in range(n) : # Iterate for all powers of two for j in range(1, 31) : # Left number lx = x[i] - (1 << j) # Right number rx = x[i] + (1 << j) if lx in x : isl = True else : isl = False if rx in x : isr = True else : isr = False # If possible to get sub-set of size 3 if (isl and isr and len(res) < 3) : res = [ lx, x[i], rx ] # If possible to get sub-set of size 2 if (isl and len(res) < 2) : res = [ lx, x[i] ] # If possible to get sub-set of size 2 if (isr and len(res) < 2) : res = [ x[i], rx ] # If not possible to get sub-set if (not len(res)) : print(-1) return # Print the sub-set for it in res : print(it, end = " ") # Driver Code if __name__ == "__main__" : a = [ 3, 4, 5, 6, 7 ] n = len(a) PowerOfTwo(a, n) # This code is contributed by Ryuga |
C#
// C# program to find sub-set with// maximum possible sizeusing System;using System.Collections;class GFG{ // Function to find sub-set with// maximum possible sizestatic void PowerOfTwo(int[] x, int n){ // Sort the given array Array.Sort(x); // To store required sub-set ArrayList res = new ArrayList(); for (int i = 0; i < n; ++i) { // Iterate for all powers of two for (int j = 1; j < 31; ++j) { // Left number int lx = x[i] - (1 << j); // Right number int rx = x[i] + (1 << j); // Predefined binary search in C# bool isl = Array.IndexOf(x, lx) < 0? false : true; bool isr = Array.IndexOf(x, rx) < 0? false : true; // If possible to get sub-set of size 3 if (isl && isr && res.Count < 3) { res.Clear(); res.Add(lx); res.Add(x[i]); res.Add(rx); } // If possible to get sub-set of size 2 if (isl && res.Count < 2) { res.Clear(); res.Add(lx); res.Add(x[i]); } // If possible to get sub-set of size 2 if (isr && res.Count < 2) { res.Clear(); res.Add(x[i]); res.Add(rx); } } } // If not possible to get sub-set if (res.Count == 0) { Console.Write("-1"); return; } // Print the sub-set for (int i = 0; i < res.Count; i++) Console.Write(res[i] + " ");}// Driver Codepublic static void Main() { int[] a = {3, 4, 5, 6, 7}; int n = a.Length; PowerOfTwo(a, n);}}// This code is Contributed by chandan_jnu |
PHP
<?php// PHP program to find sub-set with// maximum possible size// Function to find sub-set with// maximum possible sizefunction PowerOfTwo($x, $n){ // Sort the given array sort($x); // To store required sub-set $res = array(); for ($i = 0; $i < $n; ++$i) { // Iterate for all powers of two for ($j = 1; $j < 31; ++$j) { // Left number $lx = $x[$i] - (1 << $j); // Right number $rx = $x[$i] + (1 << $j); // Predefined binary search in PHP $isl = in_array($lx, $x); $isr = in_array($rx, $x); // If possible to get sub-set of size 3 if ($isl && $isr && count($res) < 3) { unset($res); $res = array(); array_push($res, $lx); array_push($res, $x[$i]); array_push($res, $rx); } // If possible to get sub-set of size 2 if ($isl && count($res) < 2) { unset($res); $res = array(); array_push($res, $lx); array_push($res, $x[$i]); } // If possible to get sub-set of size 2 if ($isr && count($res) < 2) { unset($res); $res = array(); array_push($res, $x[$i]); array_push($res, $rx); } } } // If not possible to get sub-set if (!count($res)) { echo "-1"; return; } // Print the sub-set for ($i = 0; $i < count($res); $i++) echo $res[$i] . " ";}// Driver Code$a = array( 3, 4, 5, 6, 7 );$n = count($a);PowerOfTwo($a, $n);// This code is contributed by chandan_jnu?> |
Javascript
<script> // Javascript program to find sub-set with // maximum possible size // Function to find sub-set with // maximum possible size function PowerOfTwo(x, n) { // Sort the given array x.sort(); // To store required sub-set let res = []; for (let i = 0; i < n; ++i) { // Iterate for all powers of two for (let j = 1; j < 31; ++j) { // Left number let lx = x[i] - (1 << j); // Right number let rx = x[i] + (1 << j); // Predefined binary search in Java let isl = x.indexOf(lx) < 0 ? false : true; let isr = x.indexOf(rx) < 0 ? false : true; // If possible to get sub-set of size 3 if (isl && isr && res.length < 3) { res = []; res.push(lx); res.push(x[i]); res.push(rx); } // If possible to get sub-set of size 2 if (isl && res.length < 2) { res = []; res.push(lx); res.push(x[i]); } // If possible to get sub-set of size 2 if (isr && res.length < 2) { res = []; res.push(x[i]); res.push(rx); } } } // If not possible to get sub-set if (res.length == 0) { document.write("-1" + "</br>"); return; } // Print the sub-set for (let i = 0; i < res.length; i++) document.write(res[i] + " "); } let a = [3, 4, 5, 6, 7]; let n = a.length; PowerOfTwo(a, n);// This code is contributed by mukesh07.</script> |
Output:
3 5 7
Time Complexity : O(N*logN)
Auxiliary Space : O(1), since no extra space has been taken.
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!
