Comprueba si la concatenación de los primeros N números naturales es divisible por 3

Dado un número entero N , la tarea es verificar si la concatenación de los primeros N números naturales es divisible por 3 o no. Escriba si es divisible y No si no.

Ejemplos :

Entrada : N = 3 
Salida: Sí 
Explicación: 
El número concatenado = 123 
Como es divisible por 3, la salida es Sí
Entrada : N = 7 
Salida: No 
Explicación: El número concatenado = 1234567 
Como no es divisible por 3, el la salida es No. 
 

Enfoque ingenuo
el enfoque más simple es concatenar los primeros N números naturales y calcular la suma de los dígitos del número resultante y verificar si es divisible por 3 o no. 
Complejidad de tiempo: O(N) 
Espacio auxiliar: O(1)
Enfoque eficiente: 
Para optimizar el enfoque anterior, podemos observar un patrón. La concatenación de los primeros N números naturales no es divisible por 3 para las siguientes series 1, 4, 7, 10, 13, 16, 19 , etc. El N -ésimo término de la serie viene dado por la fórmula 3×n+1 . Por lo tanto, si (N – 1)no es divisible por 3 , entonces el número resultante es divisible por 3, así que imprima . De lo contrario, imprima No.
A continuación se muestra la implementación del enfoque anterior:
 

C++

// C++ program for the above approach
#include <bits/stdc++.h>
 
using namespace std;
 
// Function that returns True if
// concatenation of first N natural
// numbers is divisible by 3
bool isDivisible(int N)
{
    // Check using the formula
    return (N - 1) % 3 != 0;
}
 
 
// Driver Code
int main()
{
    // Given Number
    int N = 6;
     
    // Function Call
    if (isDivisible(N))
        cout << ("Yes");
     
    else
        cout << ("No");
     
    return 0;
}
 
// This code is contributed by Mohit Kumar

Java

// Java program for the above approach
class GFG{
  
// Function that returns True if
// concatenation of first N natural
// numbers is divisible by 3
static boolean isDivisible(int N)
{
    // Check using the formula
    return (N - 1) % 3 != 0;
}
  
  
// Driver Code
public static void main(String[] args)
{
    // Given Number
    int N = 6;
      
    // Function Call
    if (isDivisible(N))
        System.out.println("Yes");
      
    else
        System.out.println("No");
}
}
 
// This code is contributed by Ritik Bansal

Python 3

# Python program for the above approach
 
# Function that returns True if
# concatenation of first N natural
# numbers is divisible by 3
def isDivisible(N):
 
    # Check using the formula
    return (N - 1) % 3 != 0
 
 
# Driver Code
if __name__ == "__main__":
 
    # Given Number
    N = 6
 
    # Function Call
    if (isDivisible(N)):
        print("Yes")
 
    else:
        print("No")

C#

// C# program for the above approach
using System;
class GFG{
 
// Function that returns True if
// concatenation of first N natural
// numbers is divisible by 3
static bool isDivisible(int N)
{
    // Check using the formula
    return (N – 1) % 3 != 0;
}
 
// Driver Code
public static void Main()
{
    // Given Number
    int N = 6;
     
    // Function Call
    if (isDivisible(N))
    Console.Write("Yes");
     
    else
    Console.Write("No");
}
}
 
// This code is contributed by Code_Mech

Javascript

<script>
// javascript program for the above approach
 
// Function that returns True if
// concatenation of first N natural
// numbers is divisible by 3
function isDivisible(N)
{
    // Check using the formula
    return (N - 1) % 3 != 0;
}
  
// Driver Code
 
// Given Number
var N = 6;
  
// Function Call
if (isDivisible(N))
    document.write("Yes");
else
    document.write("No");
 
// This code is contributed by Princi Singh.
</script>
Producción: 

Yes

 

Tiempo Complejidad: O(1) 
Espacio Auxiliar: O(1)
 

Publicación traducida automáticamente

Artículo escrito por spp____ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *