AND bit a bit del subarreglo más cercano a K

Dada una array entera arr[] de tamaño N y un entero K , la tarea es encontrar la array secundaria arr[i….j] donde i ≤ j y calcular el AND bit a bit de todos los elementos de la array secundaria, digamos X y luego imprimir el valor mínimo de |K – X| entre todos los valores posibles de X .

Ejemplo:  

Entrada: arr[] = {1, 6}, K = 3 
Salida: 2 
 

Sub-array	Y bit a bit	|K-X|
{1}	1	2
{6}	6	3
{dieciséis}	1	2

Entrada: arr[] = {4, 7, 10}, K = 2 
Salida: 0 
 

Método 1: 
Encuentre el AND bit a bit de todos los subconjuntos posibles y realice un seguimiento del valor mínimo posible de |K – X| .

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum possible value
// of |K - X| where X is the bitwise AND of
// the elements of some sub-array
int closetAND(int arr[], int n, int k)
{
    int ans = INT_MAX;
 
    // Check all possible sub-arrays
    for (int i = 0; i < n; i++) {
 
        int X = arr[i];
        for (int j = i; j < n; j++) {
            X &= arr[j];
 
            // Find the overall minimum
            ans = min(ans, abs(k - X));
        }
    }
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 4, 7, 10 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << closetAND(arr, n, k);
 
    return 0;
}

// Java implementation of the approach
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.io.*;
 
class GFG {
 
    // Function to return the minimum possible value
    // of |K - X| where X is the bitwise AND of
    // the elements of some sub-array
    static int closetAND(int arr[], int n, int k)
    {
        int ans = Integer.MAX_VALUE;
 
        // Check all possible sub-arrays
        for (int i = 0; i < n; i++) {
 
            int X = arr[i];
            for (int j = i; j < n; j++) {
                X &= arr[j];
 
                // Find the overall minimum
                ans = Math.min(ans, Math.abs(k - X));
            }
        }
        return ans;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 4, 7, 10 };
        int n = arr.length;
        int k = 2;
        System.out.println(closetAND(arr, n, k));
    }
}
 
// This code is contributed by jit_t

# Python implementation of the approach
 
# Function to return the minimum possible value
# of |K - X| where X is the bitwise AND of
# the elements of some sub-array
def closetAND(arr, n, k):
 
    ans = 10**9
 
    # Check all possible sub-arrays
    for i in range(n):
 
        X = arr[i]
 
        for j in range(i,n):
            X &= arr[j]
 
            # Find the overall minimum
            ans = min(ans, abs(k - X))
         
    return ans
 
# Driver code
arr = [4, 7, 10]
n = len(arr)
k = 2;
print(closetAND(arr, n, k))
 
# This code is contributed by mohit kumar 29

// C# implementation of the approach
using System;
 
class GFG
{
 
    // Function to return the minimum possible value
    // of |K - X| where X is the bitwise AND of
    // the elements of some sub-array
    static int closetAND(int []arr, int n, int k)
    {
        int ans = int.MaxValue;
 
        // Check all possible sub-arrays
        for (int i = 0; i < n; i++)
        {
 
            int X = arr[i];
            for (int j = i; j < n; j++)
            {
                X &= arr[j];
 
                // Find the overall minimum
                ans = Math.Min(ans, Math.Abs(k - X));
            }
        }
        return ans;
    }
 
    // Driver code
    public static void Main()
    {
        int []arr = { 4, 7, 10 };
        int n = arr.Length;
        int k = 2;
         
        Console.WriteLine(closetAND(arr, n, k));
    }
}
 
// This code is contributed by AnkitRai01

<?php
// PHP implementation of the approach
 
// Function to return the minimum possible value
// of |K - X| where X is the bitwise AND of
// the elements of some sub-array
function closetAND(&$arr, $n, $k)
{
    $ans = PHP_INT_MAX;
 
    // Check all possible sub-arrays
    for ($i = 0; $i < $n; $i++)
    {
 
        $X = $arr[$i];
        for ($j = $i; $j < $n; $j++)
        {
            $X &= $arr[$j];
 
            // Find the overall minimum
            $ans = min($ans, abs($k - $X));
        }
    }
    return $ans;
}
 
    // Driver code
    $arr = array( 4, 7, 10 );
    $n = sizeof($arr) / sizeof($arr[0]);
    $k = 2;
    echo closetAND($arr, $n, $k);
 
    return 0;
     
    // This code is contributed by ChitraNayal
?>

<script>
 
// Javascript implementation of the approach
 
// Function to return the minimum possible value
// of |K - X| where X is the bitwise AND of
// the elements of some sub-array
function closetAND(arr, n, k)
{
    let ans = Number.MAX_VALUE;
 
    // Check all possible sub-arrays
    for(let i = 0; i < n; i++)
    {
        let X = arr[i];
        for(let j = i; j < n; j++)
        {
            X &= arr[j];
 
            // Find the overall minimum
            ans = Math.min(ans, Math.abs(k - X));
        }
    }
    return ans;
}
 
// Driver code
let arr = [4, 7, 10 ];
let n = arr.length;
let k = 2;
 
document.write(closetAND(arr, n, k));
     
// This code is contributed by sravan kumar
 
</script>

0

Complejidad temporal: O(n ² )

Espacio Auxiliar: O(1), ya que no se requiere espacio adicional.

Método 2: 
se puede observar que mientras se realiza la operación AND en el subarreglo, el valor de X puede permanecer constante o disminuir, pero nunca aumentará. 
Por lo tanto, comenzaremos desde el primer elemento de un subarreglo y haremos AND bit a bit y compararemos |K – X| con la diferencia mínima actual hasta X ≤ K porque después |K – X| comenzará a aumentar. 

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum possible value
// of |K - X| where X is the bitwise AND of
// the elements of some sub-array
int closetAND(int arr[], int n, int k)
{
    int ans = INT_MAX;
 
    // Check all possible sub-arrays
    for (int i = 0; i < n; i++) {
 
        int X = arr[i];
        for (int j = i; j < n; j++) {
            X &= arr[j];
 
            // Find the overall minimum
            ans = min(ans, abs(k - X));
 
            // No need to perform more AND operations
            // as |k - X| will increase
            if (X <= k)
                break;
        }
    }
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 4, 7, 10 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << closetAND(arr, n, k);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
 
// Function to return the minimum possible value
// of |K - X| where X is the bitwise AND of
// the elements of some sub-array
static int closetAND(int arr[], int n, int k)
{
    int ans = Integer.MAX_VALUE;
 
    // Check all possible sub-arrays
    for (int i = 0; i < n; i++)
    {
 
        int X = arr[i];
        for (int j = i; j < n; j++)
        {
            X &= arr[j];
 
            // Find the overall minimum
            ans = Math.min(ans, Math.abs(k - X));
 
            // No need to perform more AND operations
            // as |k - X| will increase
            if (X <= k)
                break;
        }
    }
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 4, 7, 10 };
    int n = arr.length;
    int k = 2;
    System.out.println(closetAND(arr, n, k));
}
}
 
// This code is contributed by Princi Singh

# Python implementation of the approach
import sys
 
# Function to return the minimum possible value
# of |K - X| where X is the bitwise AND of
# the elements of some sub-array
def closetAND(arr, n, k):
    ans = sys.maxsize;
 
    # Check all possible sub-arrays
    for i in range(n):
 
        X = arr[i];
        for j in range(i,n):
            X &= arr[j];
 
            # Find the overall minimum
            ans = min(ans, abs(k - X));
 
            # No need to perform more AND operations
            # as |k - X| will increase
            if (X <= k):
                break;
    return ans;
 
# Driver code
arr = [4, 7, 10 ];
n = len(arr);
k = 2;
print(closetAND(arr, n, k));
 
# This code is contributed by PrinciRaj1992

// C# implementation of the approach
using System;    
     
class GFG
{
 
// Function to return the minimum possible value
// of |K - X| where X is the bitwise AND of
// the elements of some sub-array
static int closetAND(int []arr, int n, int k)
{
    int ans = int.MaxValue;
 
    // Check all possible sub-arrays
    for (int i = 0; i < n; i++)
    {
 
        int X = arr[i];
        for (int j = i; j < n; j++)
        {
            X &= arr[j];
 
            // Find the overall minimum
            ans = Math.Min(ans, Math.Abs(k - X));
 
            // No need to perform more AND operations
            // as |k - X| will increase
            if (X <= k)
                break;
        }
    }
    return ans;
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 4, 7, 10 };
    int n = arr.Length;
    int k = 2;
    Console.WriteLine(closetAND(arr, n, k));
}
}
 
// This code has been contributed by 29AjayKumar

<script>   
    // Javascript implementation of the approach
     
    // Function to return the minimum possible value
    // of |K - X| where X is the bitwise AND of
    // the elements of some sub-array
    function closetAND(arr, n, k)
    {
        let ans = Number.MAX_VALUE;
 
        // Check all possible sub-arrays
        for (let i = 0; i < n; i++)
        {
 
            let X = arr[i];
            for (let j = i; j < n; j++)
            {
                X &= arr[j];
 
                // Find the overall minimum
                ans = Math.min(ans, Math.abs(k - X));
 
                // No need to perform more AND operations
                // as |k - X| will increase
                if (X <= k)
                    break;
            }
        }
        return ans;
    }
     
    let arr = [ 4, 7, 10 ];
    let n = arr.length;
    let k = 2;
    document.write(closetAND(arr, n, k));
 
</script>

0

Complejidad temporal: O(n ² )

Espacio Auxiliar: O(1)