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 Sí 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 Sí . 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>
Yes
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)