Verifique si todos los elementos de la array se pueden convertir a K usando las operaciones dadas

Dado un arreglo de enteros arr de tamaño N y un entero K , la tarea es hacer que todos los elementos del arreglo sean iguales a K usando las siguientes operaciones: 
 

• Elija un subarreglo arbitrario [l….r] del arreglo de entrada
• Reemplace todos los valores de este subarreglo igual al [((r – l) + 2) / 2] ^th valor en el subarreglo ordenado [l…r]

Ejemplos: 
 

Entrada: arr [ ] = {5, 4, 3, 1, 2, 6, 7, 8, 9, 10}, K = 3 
Salida: SÍ 
Explicación: 
Elija los primeros cinco elementos y reemplace todos los elementos con 3: arr = { 3, 3, 3, 3, 3, 6, 7, 8, 9, 10} 
Ahora tome el sexto elemento y reemplace todos los elementos con 3: arr = {3, 3, 3, 3, 3, 3, 7, 8, 9, 10} 
Aplicando las mismas operaciones podemos hacer que todos los elementos de arr sean iguales a K: arr = {3, 3, 3, 3, 3, 3, 3, 3, 3, 3}
Entrada: arr [ ] = {3, 1, 2, 3}, K = 4 
Salida: NO 
 

Acercarse: 
 

• Podemos observar que es posible hacer que todos los elementos de la array sean iguales a K solo si se cumplen las siguientes dos condiciones: 
  1. Debe haber al menos un elemento igual a K .
  2. Debe existir un triplete continuo tal que dos valores cualesquiera de ese triplete sean mayores o iguales a K.
• Para resolver este problema, necesitamos crear una array auxiliar, digamos aux[] , que contenga tres valores 0, 1, 2.
• La tarea final es verificar si es posible hacer que todos los elementos de la array aux sean iguales a 1. Si dos de los tres elementos continuos en aux[] son ​​mayores que 0, entonces podemos tomar una subarreglo de tamaño 3 y hacer que todos los elementos de ese subarreglo igual a 1. Y luego expandimos esta lógica a través de todo el arreglo.

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

// C++ implementation of above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function that prints
// whether is to possible
// to make all elements
// of the array equal to K
void makeAllK(int a[], int k, int n)
{
    vector<int> aux;
 
    bool one_found = false;
 
    // Fill vector aux
    // according to the
    // above approach
    for (int i = 0; i < n; i++) {
 
        if (a[i] < k)
            aux.push_back(0);
 
        else if (a[i] == k) {
            aux.push_back(1);
            one_found = true;
        }
 
        else
            aux.push_back(2);
    }
 
    // Condition if K
    // does not exist in
    // the given array
    if (one_found == false) {
        cout << "NO"
             << "\n";
        return;
    }
 
    bool ans = false;
 
    if (n == 1
        && aux[0] == 1)
        ans = true;
 
    if (n == 2
        && aux[0] > 0
        && aux[1] > 1)
        ans = true;
 
    for (int i = 0; i < n - 2; i++) {
 
        // Condition for minimum
        // two elements is
        // greater than 0 in
        // pair of three elements
        if (aux[i] > 0
            && aux[i + 1] > 0) {
 
            ans = true;
            break;
        }
 
        else if (aux[i] > 0
                 && aux[i + 2] > 0) {
            ans = true;
            break;
        }
 
        else if (aux[i + 2] > 0
                 && aux[i + 1] > 0) {
            ans = true;
            break;
        }
    }
 
    if (ans == true)
        cout << "YES"
             << "\n";
    else
        cout << "NO"
             << "\n";
}
 
// Driver Code
int main()
{
    int arr[]
        = { 1, 2, 3,
            4, 5, 6,
            7, 8, 9, 10 };
 
    int K = 3;
 
    int size = sizeof(arr)
               / sizeof(arr[0]);
 
    makeAllK(arr, K, size);
 
    return 0;
}

// Java implementation of the above approach
import java.util.*;
 
class GFG{
 
// Function that prints
// whether is to possible
// to make all elements
// of the array equal to K
static void makeAllK(int a[], int k, int n)
{
    Vector<Integer> aux = new Vector<Integer>();
 
    boolean one_found = false;
 
    // Fill vector aux according
    // to the above approach
    for(int i = 0; i < n; i++)
    {
       if (a[i] < k)
           aux.add(0);
        
       else if (a[i] == k)
       {
           aux.add(1);
           one_found = true;
       }
       else
           aux.add(2);
    }
 
    // Condition if K does not 
    // exist in the given array
    if (one_found == false)
    {
        System.out.print("NO" + "\n");
        return;
    }
 
    boolean ans = false;
 
    if (n == 1 && aux.get(0) == 1)
        ans = true;
 
    if (n == 2 && aux.get(0) > 0 &&
                  aux.get(1) > 1)
        ans = true;
 
    for(int i = 0; i < n - 2; i++)
    {
        
       // Condition for minimum
       // two elements is
       // greater than 0 in
       // pair of three elements
       if (aux.get(i) > 0 &&
           aux.get(i + 1) > 0)
       {
           ans = true;
           break;
       }
       else if (aux.get(i) > 0 &&
                aux.get(i + 2) > 0)
       {
           ans = true;
           break;
       }
       else if (aux.get(i + 2) > 0 &&
                aux.get(i + 1) > 0)
       {
           ans = true;
           break;
       }
    }
 
    if (ans == true)
        System.out.print("YES" + "\n");
    else
        System.out.print("NO" + "\n");
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 1, 2, 3, 4, 5,
                  6, 7, 8, 9, 10 };
    int K = 3;
    int size = arr.length;
 
    makeAllK(arr, K, size);
 
}
}
 
// This code is contributed by amal kumar choubey

# Python3 implementation of above approach
 
# Function that prints whether is
# to possible to make all elements
# of the array equal to K
def makeAllK(a, k, n):
     
    aux = []
    one_found = False
 
    # Fill vector aux according
    # to the above approach
    for i in range(n):
        if (a[i] < k):
            aux.append(0)
 
        elif (a[i] == k):
            aux.append(1)
            one_found = True
 
        else:
            aux.append(2)
 
    # Condition if K does
    # not exist in the given
    # array
    if (one_found == False):
        print("NO")
        return
 
    ans = False
 
    if (n == 1 and aux[0] == 1):
        ans = True
 
    if (n == 2 and aux[0] > 0 and aux[1] > 1):
        ans = True
 
    for i in range(n - 2):
         
        # Condition for minimum two
        # elements is greater than
        # 0 in pair of three elements
        if (aux[i] > 0 and aux[i + 1] > 0):
            ans = True
            break
 
        elif (aux[i] > 0 and aux[i + 2] > 0):
            ans = True
            break
 
        elif (aux[i + 2] > 0 and aux[i + 1] > 0):
            ans = True
            break
 
    if (ans == True):
        print("YES")
    else:
        print("NO")
 
# Driver Code
if __name__ == '__main__':
     
    arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
    K = 3
    size = len(arr)
 
    makeAllK(arr, K, size)
 
# This code is contributed by Surendra_Gangwar

// C# implementation of the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function that prints
// whether is to possible
// to make all elements
// of the array equal to K
static void makeAllK(int []a, int k, int n)
{
    List<int> aux = new List<int>();
 
    bool one_found = false;
 
    // Fill vector aux according
    // to the above approach
    for(int i = 0; i < n; i++)
    {
       if (a[i] < k)
       {
           aux.Add(0);
       }
       else if (a[i] == k)
       {
           aux.Add(1);
           one_found = true;
       }
       else
           aux.Add(2);
    }
 
    // Condition if K does not
    // exist in the given array
    if (one_found == false)
    {
        Console.Write("NO" + "\n");
        return;
    }
 
    bool ans = false;
    if (n == 1 && aux[0] == 1)
        ans = true;
 
    if (n == 2 && aux[0] > 0 &&
                  aux[1] > 1)
        ans = true;
 
    for(int i = 0; i < n - 2; i++)
    {
        
       // Condition for minimum
       // two elements is
       // greater than 0 in
       // pair of three elements
       if (aux[i] > 0 &&
           aux[i + 1] > 0)
       {
           ans = true;
           break;
       }
       else if (aux[i] > 0 &&
                aux[i + 2] > 0)
       {
           ans = true;
           break;
       }
       else if (aux[i + 2] > 0 &&
                aux[i + 1] > 0)
       {
           ans = true;
           break;
       }
    }
    if (ans == true)
        Console.Write("YES" + "\n");
    else
        Console.Write("NO" + "\n");
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 1, 2, 3, 4, 5,
                  6, 7, 8, 9, 10 };
    int K = 3;
    int size = arr.Length;
 
    makeAllK(arr, K, size);
}
}
 
// This code is contributed by amal kumar choubey

<script>
 
// Javascript implementation of above approach
 
// Function that prints
// whether is to possible
// to make all elements
// of the array equal to K
function makeAllK(a, k, n)
{
    var aux = [];
 
    var one_found = false;
 
    // Fill vector aux
    // according to the
    // above approach
    for (var i = 0; i < n; i++) {
 
        if (a[i] < k)
            aux.push(0);
 
        else if (a[i] == k) {
            aux.push(1);
            one_found = true;
        }
 
        else
            aux.push(2);
    }
 
    // Condition if K
    // does not exist in
    // the given array
    if (one_found == false) {
        document.write( "NO" + "<br>");
        return;
    }
 
    var ans = false;
 
    if (n == 1
        && aux[0] == 1)
        ans = true;
 
    if (n == 2
        && aux[0] > 0
        && aux[1] > 1)
        ans = true;
 
    for (var i = 0; i < n - 2; i++) {
 
        // Condition for minimum
        // two elements is
        // greater than 0 in
        // pair of three elements
        if (aux[i] > 0
            && aux[i + 1] > 0) {
 
            ans = true;
            break;
        }
 
        else if (aux[i] > 0
                 && aux[i + 2] > 0) {
            ans = true;
            break;
        }
 
        else if (aux[i + 2] > 0
                 && aux[i + 1] > 0) {
            ans = true;
            break;
        }
    }
 
    if (ans == true)
        document.write( "YES"+ "<br>")
    else
        document.write( "NO"+ "<br>")
}
 
// Driver Code
var arr
    = [1, 2, 3,
        4, 5, 6,
        7, 8, 9, 10];
var K = 3;
var size = arr.length;
makeAllK(arr, K, size);
 
// This code is contributed by rutvik_56.
</script>

YES

Complejidad temporal: O(N)  
Espacio auxiliar: O(N)