Modifique la secuencia de los primeros N números naturales en una array dada reemplazando los pares con su GCD

Dado un número entero N y una array arr[] , la tarea es verificar si una secuencia de los primeros N números naturales, es decir, {1, 2, 3, .. N} puede hacerse igual a arr[] eligiendo cualquier par ( i, j) de la secuencia y reemplazando tanto i como j por GCD de i y j . Si es posible, escriba «Sí» . De lo contrario, escriba “No” .

Ejemplos:

Entrada: N = 4, arr[] = {1, 2, 3, 2}
Salida: Sí
Explicación: Para el par (2, 4) en la secuencia {1, 2, 3, 4}, MCD(2, 4 ) = 2. Ahora, la secuencia se modifica a {1, 2, 3, 2}, que es lo mismo que arr[].

Entrada: N = 3, arr[] = {1, 2, 2}
Salida: No

Enfoque: La idea se basa en el hecho de que el MCD de dos números se encuentra entre 1 y el mínimo de los dos números . Por definición de mcd, es el mayor número que divide a ambos. Por lo tanto, haga que el número en un índice sea más pequeño si y solo si existe algún número que sea su factor. Por lo tanto, se puede concluir que para cada i ^-ésimo índice en la array, si la condición de seguimiento se cumple, la array arr[] se puede obtener de la secuencia de los primeros N números naturales.

(i + 1) % arreglo[i] == 0

Siga los pasos a continuación para resolver el problema: 

• Recorra la array arr[] usando la variable i.
• Para cada i ^-ésimo índice, verifique si ( i + 1) % arr[i] es igual a 0 o no. Si se encuentra que es falso para cualquier elemento de la array, imprima «No» .
• De lo contrario, después de recorrer completamente la array, imprima «Sí» .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if array arr[]
// can be obtained from first N
// natural numbers or not
void isSequenceValid(vector<int>& B,
                     int N)
{
    for (int i = 0; i < N; i++) {
 
        if ((i + 1) % B[i] != 0) {
            cout << "No";
            return;
        }
    }
 
    cout << "Yes";
}
 
// Driver Code
int main()
{
    int N = 4;
    vector<int> arr{ 1, 2, 3, 2 };
 
    // Function Call
    isSequenceValid(arr, N);
 
    return 0;
}

// Java program for the above approach
class GFG{
      
// Function to check if array arr[]
// can be obtained from first N
// natural numbers or not
static void isSequenceValid(int[] B,
                            int N)
{
    for(int i = 0; i < N; i++)
    {
        if ((i + 1) % B[i] != 0)
        {
            System.out.print("No");
            return;
        }
    }
    System.out.print("Yes");
}
  
// Driver code
public static void main(String[] args)
{
    int N = 4;
    int[] arr = { 1, 2, 3, 2 };
     
    // Function Call
    isSequenceValid(arr, N);
}
}
  
// This code is contributed by sanjoy_62

# Python3 program for the above approach
 
# Function to check if array arr[]
# can be obtained from first N
# natural numbers or not
def isSequenceValid(B, N):
     
    for i in range(N):
        if ((i + 1) % B[i] != 0):
            print("No")
            return
         
    print("Yes")
     
# Driver Code
N = 4
arr = [ 1, 2, 3, 2 ]
  
# Function Call
isSequenceValid(arr, N)
 
# This code is contributed by susmitakundugoaldanga

// C# program for the above approach
using System;
 
class GFG{
       
// Function to check if array arr[]
// can be obtained from first N
// natural numbers or not
static void isSequenceValid(int[] B,
                            int N)
{
    for(int i = 0; i < N; i++)
    {
        if ((i + 1) % B[i] != 0)
        {
            Console.WriteLine("No");
            return;
        }
    }
    Console.WriteLine("Yes");
}
   
// Driver code
public static void Main()
{
    int N = 4;
    int[] arr = { 1, 2, 3, 2 };
      
    // Function Call
    isSequenceValid(arr, N);
}
}
 
// This code is contributed by code_hunt

<script>
// Javascript program to implement
// the above approach
 
// Function to check if array arr[]
// can be obtained from first N
// natural numbers or not
function isSequenceValid(B, N)
{
    for(let i = 0; i < N; i++)
    {
        if ((i + 1) % B[i] != 0)
        {
            document.write("No");
            return;
        }
    }
    document.write("Yes");
}
 
// Driver code
 
    let N = 4;
    let arr = [ 1, 2, 3, 2 ];
      
    // Function Call
    isSequenceValid(arr, N);
     
    // This code is contributed by souravghosh0416.
</script>

Yes

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