Given an integer N, the task is to check if the concatenation of first N natural numbers is divisible by 3 or not. Print Yes if divisible and No if not.
Examples:
Input: N = 3
Output: Yes
Explanation:
The concatenated number = 123
Since it is divisible by 3, the output is YesInput: N = 7
Output: No
Explanation: The concatenated number = 1234567
Since it is not divisible by 3, the output is No.
Brute Force Approach:
A brute force approach to solve this problem would be to generate the concatenation of the first N natural numbers and then check if it is divisible by 3 or not. We can use a string to store the concatenation and then convert it into an integer for checking the divisibility.
Below is the implementation of the above approach:
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 3bool isDivisible(int N){ string concat = ""; for(int i = 1; i <= N; i++){ concat += to_string(i); } int num = stoi(concat); return (num % 3 == 0);}// Driver Codeint main(){ // Given Number int N = 6; // Function Call if (isDivisible(N)) cout << ("Yes"); else cout << ("No"); return 0;} |
Java
import java.util.*;public class Main { // Function that returns True if // concatenation of first N natural // numbers is divisible by 3 public static boolean isDivisible(int N) { String concat = ""; for (int i = 1; i <= N; i++) { concat += Integer.toString(i); } int num = Integer.parseInt(concat); return (num % 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"); } }} |
Python3
# Python code of the above approac# Defining the Function that returns True if# concatenation of first N natural# numbers is divisible by 3def isDivisible(n : int) -> bool: concat = "" for i in range(1,n+1): concat += str(i) num = int(concat) return num % 3 == 0# Driver Coden = 6# Storing the resultres = isDivisible(n)# Checking if the value# stored in variable res# is either False# or Trueif res == False: print("No")else: print("Yes") |
C#
using System;public class MainClass{ // Function that returns True if // concatenation of first N natural // numbers is divisible by 3 public static bool isDivisible(int N) { string concat = ""; for(int i = 1; i <= N; i++){ concat += i.ToString(); } int num = int.Parse(concat); return (num % 3 == 0); } // Driver Code public static void Main() { // Given Number int N = 6; // Function Call if (isDivisible(N)) Console.WriteLine("Yes"); else Console.WriteLine("No"); }} |
Javascript
function isDivisible(N) {let concat = "";for (let i = 1; i <= N; i++) {concat += i.toString();}let num = parseInt(concat);return (num % 3 === 0);}// Driver Codelet N = 6;if (isDivisible(N))console.log("Yes");elseconsole.log("No"); |
Yes
Time Complexity: O(N)
Auxiliary Space:: O(1)
Efficient Approach:
To optimize the above approach, we can observe a pattern. The concatenation of first N natural numbers is not divisible by 3 for the following series 1, 4, 7, 10, 13, 16, 19, and so on. The Nth term of the series is given by the formula 3×n +1. Hence, if (N – 1) is not divisible by 3, then the resultant number is divisible by 3, so print Yes. Otherwise, print No.
Below is the implementation of the above approach:
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 3bool isDivisible(int N){ // Check using the formula return (N - 1) % 3 != 0;}// Driver Codeint 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 approachclass GFG{ // Function that returns True if// concatenation of first N natural// numbers is divisible by 3static boolean isDivisible(int N){ // Check using the formula return (N - 1) % 3 != 0;} // Driver Codepublic 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 3def isDivisible(N): # Check using the formula return (N - 1) % 3 != 0# Driver Codeif __name__ == "__main__": # Given Number N = 6 # Function Call if (isDivisible(N)): print("Yes") else: print("No") |
C#
// C# program for the above approachusing System;class GFG{// Function that returns True if// concatenation of first N natural// numbers is divisible by 3static bool isDivisible(int N){ // Check using the formula return (N – 1) % 3 != 0;}// Driver Codepublic 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 3function isDivisible(N){ // Check using the formula return (N - 1) % 3 != 0;} // Driver Code// Given Numbervar N = 6; // Function Callif (isDivisible(N)) document.write("Yes");else document.write("No");// This code is contributed by Princi Singh. </script> |
Yes
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
