Subconjunto más grande donde la diferencia absoluta de dos elementos cualquiera es una potencia de 2

Dada una array arr[] de distintos elementos -10 ⁹ ≤ a _i ≤ 10 ⁹ . La tarea es encontrar el subconjunto más grande de la array dada de modo que la diferencia absoluta entre dos números cualesquiera en el subconjunto sea una potencia positiva de dos. Si no es posible crear dicho subconjunto, imprima -1 .
Ejemplos: 
 

Entrada: arr[] = {3, 4, 5, 6, 7} 
Salida: 3 5 7 
|3 – 5| = 2 ¹ , |5 – 7| = 2 ¹ y |3 – 7| = 2 ² .
Entrada: arr[] = {2, 5, 8} 
Salida: -1 
 

Enfoque: Probemos que el tamaño del subconjunto no será > 3 . Supongamos que a , b , c y d son cuatro elementos de un subconjunto y a < b < c < d . 
Sean abs(a – b) = 2 ^k y abs(b – c) = 2 ^l entonces abs(a – c) = abs(a – b) + abs(b – c) = 2 ^k + 2 ^l = 2 ^m . Significa que k = l . Las condiciones también deben cumplirse para el triple (b, c, d) . Ahora es fácil ver que si abs(a – b) = abs(b – c) = abs(c – d) = 2 ^k entoncesabs(a – d) = abs(a – b) * 3 que no es una potencia de dos. Entonces el tamaño del subconjunto nunca será mayor a 3. 
 

• Comprobemos si la respuesta es 3 . Iterar sobre la array dada para elementos intermedios del subconjunto y para potencias de dos de 1 a 30 inclusive. Sea xi el elemento medio del subconjunto y j la potencia actual de dos. Entonces, si hay elementos x _i -2 _j y x _i +2 _j en la array, entonces la respuesta es 3 .
• De lo contrario, compruebe si la respuesta es 2 . repita el paso anterior pero aquí uno puede obtener el punto izquierdo x _i -2 _j o x _i +2 _j .
• Si la respuesta no es ni 2 ni 3 , imprima -1 .

A continuación se muestra la implementación del enfoque anterior: 
 

// 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 size
void 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 Code
int main()
{
 
    vector<int> a = { 3, 4, 5, 6, 7 };
 
    int n = a.size();
    PowerOfTwo(a, n);
 
    return 0;
}

// Java program to find sub-set with
// maximum possible size
import java.util.*;
 
class GFG
{
     
// Function to find sub-set with
// maximum possible size
static 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 Code
public 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 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# program to find sub-set with
// maximum possible size
using System;
using System.Collections;
 
class GFG
{
     
// Function to find sub-set with
// maximum possible size
static 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 Code
public 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 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
    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
?>

<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>

3 5 7

Complejidad de Tiempo: O(N*logN) 
Espacio Auxiliar: O(1), ya que no se ha tomado ningún espacio extra.