Given a number a N and the task is to check whether the sum of absolute difference of adjacent digit is a prime or not.
Examples:
Input: N = 142
Output: Prime
Sum = |1-4| + |4-2| = 5 i.e. prime.
Input: N = 347
Output: Not prime
Approach: Find the sum of absolute difference of adjacent digits and then check if that sum is prime or not.
Algorithm:
Step 1: Start
Step 2: Create a static function of boolean return type named “prime” which takes an integer value as input and checks if the number is prime or not.
a. in the prime function there are conditions i.e if n==q returns false because 1 is not prime.
b. start a for loop from i=2 to i*i < n and check if (n % i) == 0 then it is not prime if not then prime.
Step 3: Create a static function of boolean return type name it as “checkSumPrime” which takes a string value as input return if the sum of the array is prime or not.
a. initialize an int variable name as “summ” with 0.
b. start a for loop from i=1 to the length of the string
1. The variable summ should be updated to include the absolute difference between the i-th and (i-1)-th characters.
c. check if summ is prime or not return if prime and false if not.
Step 4: End
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include<bits/stdc++.h>using namespace std;// Function to check for a prime numberbool Prime(int n){ if( n == 1){ return false; } for (int i=2;i*i<=n;i++){ if (n % i == 0) return false; } return true;}// Function to find the sum of arraybool checkSumPrime(string st){ int summ = 0; for (int i=1;i<st.size();i++) summ+= abs(st[i-1]-st[i]); if(Prime(summ)) return true; else return false;}// Driver codeint main(){ int num = 142; string s= "142"; if (checkSumPrime(s)) cout<<"Prime\n"; else cout<<"Not Prime\n";return 0;} |
Java
// Java implementation of the above approach import java.util.*;class GFG { // Function to check for a prime number static boolean Prime(int n) { if (n == 1) return false; for (int i = 2; i * i <= n; i++) if (n % i == 0) return false; return true; } // Function to find the sum of array static boolean checkSumPrime(String str) { int summ = 0; for (int i = 1; i < str.length(); i++) summ += Math.abs(str.charAt(i - 1) - str.charAt(i)); if (Prime(summ)) return true; else return false; } // Driver Code public static void main(String[] args) { int num = 142; String str = "142"; if (checkSumPrime(str)) System.out.println("Prime"); else System.out.println("Not Prime"); }}// This code is contributed by// sanjeev2552 |
Python3
# Python3 implementation of the above approachimport math as mt# Function to check for a prime numberdef Prime(n): if n == 1: return False for i in range(2, mt.ceil(mt.sqrt(n + 1))): if n % i == 0: return False return True # Function to find the sum of arraydef checkSumPrime(string): summ = 0 for i in range(1, len(string)): summ += abs(int(string[i - 1]) - int(string[i])) if Prime(summ): return True else: return False# Driver codenum = 142string = str(num)s = [i for i in string]if checkSumPrime(s): print("Prime")else: print("Not Prime\n")# This code is contributed by Mohit Kumar |
C#
// C# implementation of the above approach using System; class GFG { // Function to check for a prime number static bool Prime(int n) { if (n == 1) return false; for (int i = 2; i * i <= n; i++) if (n % i == 0) return false; return true; } // Function to find the sum of array static bool checkSumPrime(String str) { int summ = 0; for (int i = 1; i < str.Length; i++) summ += Math.Abs(str[i - 1] - str[i]); if (Prime(summ)) return true; else return false; } // Driver Code public static void Main(String[] args) { String str = "142"; if (checkSumPrime(str)) Console.WriteLine("Prime"); else Console.WriteLine("Not Prime"); }}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript implementation of the above approach// Function to check for a prime numberfunction Prime(n){ if (n == 1) return false; for(let i = 2; i * i <= n; i++) if (n % i == 0) return false; return true;}// Function to find the sum of arrayfunction checkSumPrime(str){ let summ = 0; for(let i = 1; i < str.length; i++) summ += Math.abs(str[i - 1]- str[i]); if (Prime(summ)) return true; else return false;}// Driver Codelet num = 142;let str = "142";if (checkSumPrime(str)) document.write("Prime");else document.write("Not Prime"); // This code is contributed by unknown2108</script> |
Prime
Time Complexity: O(sum1/2), where the sum is the sum of the digits of the number
Auxiliary Space: O(1)
METHOD 2 :Using re module
APPRAOCH:
The code checks whether the sum of the absolute difference between adjacent digits in a number is a prime number or not.
ALGORITHM:
1.Convert the input number to a list of its digits.
2.Calculate the sum of the absolute difference between adjacent digits in the list.
3.Check if the sum is a prime number using a separate function is_prime.
4.Return True if the sum is prime, False otherwise.
C++
#include <iostream>#include <cmath>#include <regex>using namespace std;bool is_prime(int n) { if (n < 2) { return false; } for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) { return false; } } return true;}bool is_prime_sum_adjacent_digits(int n) { string numStr = to_string(n); regex digitsRegex("\\d"); smatch match; vector<int> digits; while (regex_search(numStr, match, digitsRegex)) { digits.push_back(stoi(match.str())); numStr = match.suffix(); } int diffSum = 0; for (int i = 0; i < digits.size() - 1; i++) { diffSum += abs(digits[i] - digits[i+1]); } return is_prime(diffSum);}int main() { int n = 142; if (is_prime_sum_adjacent_digits(n)) { cout << "Prime" << endl; } else { cout << "Not prime" << endl; } n = 347; if (is_prime_sum_adjacent_digits(n)) { cout << "Prime" << endl; } else { cout << "Not prime" << endl; } return 0;} |
Java
/*package whatever //do not write package name here */import java.util.regex.Matcher;import java.util.regex.Pattern;public class GFG { public static boolean isPrime(int n) { if (n < 2) { return false; } for (int i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) { return false; } } return true; } public static boolean isPrimeSumAdjacentDigits(int n) { String nString = Integer.toString(n); Matcher matcher = Pattern.compile("\\d").matcher(nString); int[] digits = new int[nString.length()]; int i = 0; while (matcher.find()) { digits[i++] = Integer.parseInt(matcher.group()); } int diffSum = 0; for (int j = 0; j < digits.length - 1; j++) { diffSum += Math.abs(digits[j] - digits[j + 1]); } return isPrime(diffSum); } public static void main(String[] args) { int n = 142; if (isPrimeSumAdjacentDigits(n)) { System.out.println("Prime"); } else { System.out.println("Not prime"); } n = 347; if (isPrimeSumAdjacentDigits(n)) { System.out.println("Prime"); } else { System.out.println("Not prime"); } }} |
Python3
import redef is_prime(n): if n < 2: return False for i in range(2, int(n**0.5)+1): if n % i == 0: return False return Truedef is_prime_sum_adjacent_digits(n): digits = [int(d) for d in re.findall('\d', str(n))] diff_sum = sum(abs(digits[i] - digits[i+1]) for i in range(len(digits)-1)) return is_prime(diff_sum)# Example usage:n = 142if is_prime_sum_adjacent_digits(n): print("Prime")else: print("Not prime")n = 347if is_prime_sum_adjacent_digits(n): print("Prime")else: print("Not prime") |
C#
using System;using System.Text.RegularExpressions;class GFG{ // Function to check if a number is prime public static bool IsPrime(int n) { if (n < 2) { return false; } for (int i = 2; i <= Math.Sqrt(n); i++) { if (n % i == 0) { return false; } } return true; } // Function to check if the sum of adjacent digits' // differences is prime public static bool IsPrimeSumAdjacentDigits(int n) { // Convert the number to a string to extract individual digits string nString = n.ToString(); // Use regular expression to find all individual digits MatchCollection matches = Regex.Matches(nString, @"\d"); // Create an array to store the extracted digits int[] digits = new int[nString.Length]; int i = 0; // Convert the matched digits back to integers and store // them in the array foreach (Match match in matches) { digits[i++] = int.Parse(match.Value); } // Calculate the sum of absolute differences between // adjacent digits int diffSum = 0; for (int j = 0; j < digits.Length - 1; j++) { diffSum += Math.Abs(digits[j] - digits[j + 1]); } // Check if the sum of differences is prime using // the IsPrime function return IsPrime(diffSum); } public static void Main(string[] args) { int n = 142; // Check if the sum of adjacent digits' differences is // prime for the number 142 if (IsPrimeSumAdjacentDigits(n)) { Console.WriteLine("Prime"); } else { Console.WriteLine("Not prime"); } n = 347; // Check if the sum of adjacent digits' differences is // prime for the number 347 if (IsPrimeSumAdjacentDigits(n)) { Console.WriteLine("Prime"); } else { Console.WriteLine("Not prime"); } }} |
Javascript
function isPrime(n) { if (n < 2) { return false; } for (let i = 2; i <= Math.sqrt(n); i++) { if (n % i === 0) { return false; } } return true;}function isPrimeSumAdjacentDigits(n) { const nString = n.toString(); const digits = nString.split('').map(Number); let diffSum = 0; for (let j = 0; j < digits.length - 1; j++) { diffSum += Math.abs(digits[j] - digits[j + 1]); } return isPrime(diffSum);}// Test caseslet n = 142;if (isPrimeSumAdjacentDigits(n)) { console.log("Prime");} else { console.log("Not prime");}n = 347;if (isPrimeSumAdjacentDigits(n)) { console.log("Prime");} else { console.log("Not prime");} |
Prime Not prime
Time complexity is O(log n * sqrt(n)).
Space complexity: The code uses a list to store the digits of the input number, which takes O(log n) space, where n is the input number.
Approach:
1. We include the necessary headers and declare functions to generate a prime sieve, check if a number is prime, calculate the sum of absolute differences of adjacent digits, and check if a sum is prime.
2. In the `main` function, we generate the prime sieve up to the maximum possible sum based on the number of digits in the input number.
3. We calculate the sum of absolute differences of adjacent digits in the input number.
4. Using the prime sieve, we check if the calculated sum is prime.
5. Based on the result, we output whether the sum is prime or not.
C++
#include <iostream>#include <vector>using namespace std;// Function to generate the prime sievevector<bool> generateSieve(int limit) { vector<bool> sieve(limit + 1, true); sieve[0] = sieve[1] = false; for (int p = 2; p * p <= limit; ++p) { if (sieve[p]) { for (int i = p * p; i <= limit; i += p) { sieve[i] = false; } } } return sieve;}// Function to check if a number is primebool isPrime(int n, const vector<bool>& sieve) { return sieve[n];}// Function to calculate the sum of absolute differences of adjacent digitsint calculateSumOfAbsoluteDifferences(int N) { int sum = 0; int prevDigit = N % 10; N /= 10; while (N > 0) { int currDigit = N % 10; sum += abs(currDigit - prevDigit); prevDigit = currDigit; N /= 10; } return sum;}// Function to check if the sum is prime or notbool isSumPrime(int sum, const vector<bool>& sieve) { return isPrime(sum, sieve);}int main() { int N = 142; // Generate sieve of primes up to the maximum possible sum int maxSum = 9 * (to_string(N).length() - 1); vector<bool> sieve = generateSieve(maxSum); // Calculate the sum of absolute differences int sum = calculateSumOfAbsoluteDifferences(N); // Check if the sum is prime or not bool isPrimeSum = isSumPrime(sum, sieve); if (isPrimeSum) { cout << "Prime" << endl; } else { cout << "Not Prime" << endl; } return 0;} |
Prime
Time Complexity:
Generating the prime sieve using the Sieve of Eratosthenes algorithm takes O(N log log N), where N is the maximum possible sum of absolute differences. This is because we iterate up to the square root of N to mark the multiples of prime numbers.
Auxiliary Space:
The space complexity is primarily determined by the size of the prime sieve, which is O(N), where N is the maximum possible sum of absolute differences.
You’ll access excellent video content by our CEO, Sandeep Jain, tackle common interview questions, and engage in real-time coding contests covering various DSA topics. We’re here to prepare you thoroughly for online assessments and interviews.
Ready to dive in? Explore our free demo content and join our DSA course, trusted by over 100,000neveropen! Whether it’s DSA in C++, Java, Python, or JavaScript we’ve got you covered. Let’s embark on this exciting journey together!
