Check if a Linked List is an Armstrong Number
Given a singly linked list List containing N nodes representing a number, the task is to check whether the given linked list is an Armstrong number. Print “1” if the given linked list is an Armstrong number, else print “0”.
Note: An Armstrong number is a number that is equal to the sum of its own digits each raised to the power of the number of digits.
Examples:
Input: List = 1 -> 5 -> 3
Output: 1
Explanation: 153 is an Armstrong number because 1^3 + 5^3 + 3^3 = 153Input: List = 2 -> 7 -> 8
Output: 0
Naive Approach: This problem can be solved using string manipulation.
- To implement this approach, we first need to convert the linked list into a string. We can do this by iterating over the linked list and appending each digit to a string.
- Once we have the string representation of the linked list, iterate over the string and convert each character to an integer.
- Then raise it to the power of the number of digits and add it to the sum.
- Finally, we can compare the sum with the integer representation of the linked list to determine if it is an Armstrong number.
Below is the code for the above approach:
C++
// C++ implementation to check if // Linked List is an Armstrong Number #include <bits/stdc++.h> using namespace std; // Define a Node class to represent // nodes in the linked list class Node { public : int data; Node* next; Node( int data) { this ->data = data; next = NULL; } }; // Define a function to convert // the linked list to a string string listToString(Node* head) { string result = "" ; Node* curr = head; while (curr != NULL) { result += to_string(curr->data); curr = curr->next; } return result; } // Define a function to check if the // linked list is an Armstrong number bool isArmstrongNumber(Node* head) { // Convert the linked list // to a string string str = listToString(head); // Count the number of digits // in the linked list int n = str.length(); // Calculate the sum of the digits // raised to the power of // the number of digits int sum = 0; for ( int i = 0; i < n; i++) { int digit = str[i] - '0' ; sum += pow (digit, n); } // Calculate the integer representation // of the linked list int num = stoi(str); // Compare the sum and the integer // representation and return the result return num == sum; } // Drivers code int main() { // Create a linked list and check if // it's an Armstrong number Node* head = new Node(1); head->next = new Node(5); head->next->next = new Node(3); cout << isArmstrongNumber(head) << endl; // Output: 1 (true) return 0; } |
Java
import java.util.*; // Define a Node class to represent // nodes in the linked list class Node { int data; Node next; Node( int data) { this .data = data; next = null ; } } class Main { // Define a function to convert // the linked list to a string static String listToString(Node head) { String result = "" ; Node curr = head; while (curr != null ) { result += Integer.toString(curr.data); curr = curr.next; } return result; } // Define a function to check if the // linked list is an Armstrong number static boolean isArmstrongNumber(Node head) { // Convert the linked list to a string String str = listToString(head); // Count the number of digits in the linked list int n = str.length(); // Calculate the sum of the digits raised to the power of // the number of digits int sum = 0 ; for ( int i = 0 ; i < n; i++) { int digit = str.charAt(i) - '0' ; sum += Math.pow(digit, n); } // Calculate the integer representation of the linked list int num = Integer.parseInt(str); // Compare the sum and the integer representation and return the result return num == sum; } // Driver code public static void main(String[] args) { // Create a linked list and check if it's an Armstrong number Node head = new Node( 1 ); head.next = new Node( 5 ); head.next.next = new Node( 3 ); System.out.println(isArmstrongNumber(head)); // Output: true } } // This code is contributed by Prajwal Kandekar |
Python3
# Python implementation to check if # Linked List is an Armstrong Number # Define a Node class to represent # nodes in the linked list class Node: def __init__( self , data): self .data = data self . next = None # Define a function to convert # the linked list to a string def listToString(head): result = "" curr = head while curr ! = None : result + = str (curr.data) curr = curr. next return result # Define a function to check if the # linked list is an Armstrong number def isArmstrongNumber(head): # Convert the linked list # to a string str = listToString(head) # Count the number of digits # in the linked list n = len ( str ) # Calculate the sum of the digits # raised to the power of # the number of digits sum = 0 for i in range (n): digit = int ( str [i]) sum + = pow (digit, n) # Calculate the integer representation # of the linked list num = int ( str ) # Compare the sum and the integer # representation and return the result return int (num = = sum ) # Drivers code if __name__ = = "__main__" : # Create a linked list and check if # it's an Armstrong number head = Node( 1 ) head. next = Node( 5 ) head. next . next = Node( 3 ) print (isArmstrongNumber(head)) # Output: 1 (true) # This code is contributed by rutikbhosale |
Javascript
// JavaScript implementation to check if // Linked List is an Armstrong Number // Define a Node class to represent // nodes in the linked list class Node { constructor(data) { this .data = data; this .next = null ; } } // Define a function to convert // the linked list to a string function listToString(head) { let result = "" ; let curr = head; while (curr !== null ) { result += curr.data.toString(); curr = curr.next; } return result; } // Define a function to check if the // linked list is an Armstrong number function isArmstrongNumber(head) { // Convert the linked list // to a string let str = listToString(head); // Count the number of digits // in the linked list let n = str.length; // Calculate the sum of the digits // raised to the power of // the number of digits let sum = 0; for (let i = 0; i < n; i++) { let digit = parseInt(str[i]); sum += Math.pow(digit, n); } // Calculate the integer representation // of the linked list let num = parseInt(str); // Compare the sum and the integer // representation and return the result return num == sum; } // Driver's code // Create a linked list and check if // it's an Armstrong number let head = new Node(1); head.next = new Node(5); head.next.next = new Node(3); // Function call if (isArmstrongNumber(head)) console.log(1); else console.log(0); |
C#
// C# implementation to check if Linked List is an Armstrong // Number using System; // Define a Node class to represent nodes in the linked list class Node { public int data; public Node next; public Node( int data) { this .data = data; next = null ; } } public class GFG { // Define a function to convert the linked list to a // string static string listToString(Node head) { string result = "" ; Node curr = head; while (curr != null ) { result += curr.data.ToString(); curr = curr.next; } return result; } // Define a function to check if the linked list is an // Armstrong number static bool isArmstrongNumber(Node head) { // Convert the linked list to a string string str = listToString(head); // Count the number of digits in the linked list int n = str.Length; // Calculate the sum of the digits raised to the // power of the number of digits int sum = 0; for ( int i = 0; i < n; i++) { int digit = str[i] - '0' ; sum += ( int )Math.Pow(digit, n); } // Calculate the integer representation of the // linked list int num = Int32.Parse(str); // Compare the sum and the integer representation // and return the result return num == sum; } static public void Main() { // Code // Create a linked list and check if it's an // Armstrong number Node head = new Node(1); head.next = new Node(5); head.next.next = new Node(3); Console.WriteLine(isArmstrongNumber(head) ? 1 : 0); // Output: 1 } } // This code is contributed by lokesh. |
1
Time Complexity: O(n), to convert the linked list into a string and O(n) to calculate the sum of the digits raised to the power of the number of digits using string manipulation, giving it an overall time complexity of O(n).
Auxiliary Space: O(n), converting the linked list into a string requires extra memory to store the string.
Efficient Approach: To solve the problem efficiently follow the below idea:
Count the number of digits in the linked list using a separate function. Then, it calculates the sum of the digits raised to the power of the number of digits and also calculates the integer representation of the linked list. Finally, it compares the sum and the integer representation and returns true if they are equal, indicating that the linked list is an Armstrong number, and false otherwise.
Below are the steps for the above approach:
- Count the number of digits in the linked list using a separate function by iterating the linked list and keeping a count of the number of nodes.
- Initialize a variable say sum = 0 to store the sum of the digits raised to the power of the number of digits.
- Iterate the linked list using a pointer say curr, and keep adding the current number raised to the power of the number of digits in the linked list to variable sum using the pow() function to calculate the power of each digit, which has a time complexity of O(log n), where n is the number of bits required to represent the exponent.
- However, in this case, the maximum value of the exponent is equal to the number of digits in the linked list, which is typically a small number, so the time complexity of the pow() function can be considered constant.
- sum += pow(curr -> data, n)
- However, in this case, the maximum value of the exponent is equal to the number of digits in the linked list, which is typically a small number, so the time complexity of the pow() function can be considered constant.
- Initialize a variable say num to store the integer representation of the linked list.
- Iterate the linked list to calculate the integer representation of the linked list and keep updating variable num,
- num = num * 10 + curr -> data.
- Compare the sum and the integer representation and return the result,
- If num == sum, return 1 else return 0.
Below is the code for the above approach:
C++
// C++ implementation to check if // Linked List is an Armstrong Number #include <bits/stdc++.h> using namespace std; // Define a Node class to represent nodes // in the linked list class Node { public : int data; Node* next; Node( int data) { this ->data = data; next = NULL; } }; // Define a function to count the number // of digits in the linked list int countDigits(Node* head) { int count = 0; while (head != NULL) { count++; head = head->next; } return count; } // Define a function to check if the // linked list is an Armstrong number bool isArmstrongNumber(Node* head) { // Count the number of digits // in the linked list int n = countDigits(head); // Calculate the sum of the digits // raised to the power of // the number of digits int sum = 0; Node* curr = head; while (curr != NULL) { sum += pow (curr->data, n); curr = curr->next; } // Calculate the integer representation // of the linked list int num = 0; curr = head; while (curr != NULL) { num = num * 10 + curr->data; curr = curr->next; } // Compare the sum and the integer // representation and return the result return num == sum; } // Drivers code int main() { // Create a linked list and check // if it's an Armstrong number Node* head = new Node(1); head->next = new Node(5); head->next->next = new Node(3); cout << isArmstrongNumber(head) << endl; // Output: 1 (true) return 0; } |
Java
/*package whatever //do not write package name here */ import java.util.*; // Define a Node class to represent nodes in the linked list class Node { int data; Node next; Node( int data) { this .data = data; next = null ; } } // Define a function to count the number of digits in the linked list class LinkedList { static int countDigits(Node head) { int count = 0 ; while (head != null ) { count++; head = head.next; } return count; } // Define a function to check if the linked list is an Armstrong number static boolean isArmstrongNumber(Node head) { // Count the number of digits in the linked list int n = countDigits(head); // Calculate the sum of the digits raised to the power of the number of digits int sum = 0 ; Node curr = head; while (curr != null ) { sum += Math.pow(curr.data, n); curr = curr.next; } // Calculate the integer representation of the linked list int num = 0 ; curr = head; while (curr != null ) { num = num * 10 + curr.data; curr = curr.next; } // Compare the sum and the integer representation and return the result return num == sum; } // Drivers code public static void main(String[] args) { // Create a linked list and check if it's an Armstrong number Node head = new Node( 1 ); head.next = new Node( 5 ); head.next.next = new Node( 3 ); System.out.println(isArmstrongNumber(head)); // Output: true } } |
Python3
#python code for the above approach # Define a Node class to represent nodes in the linked list class Node: def __init__( self , data): self .data = data self . next = None # Define a function to count the number of digits in the linked list def countDigits(head): count = 0 while head: count + = 1 head = head. next return count # Define a function to check if the linked list is an Armstrong number def isArmstrongNumber(head): # Count the number of digits in the linked list n = countDigits(head) # Calculate the sum of the digits raised to the power of the number of digits sum = 0 curr = head while curr: sum + = curr.data * * n curr = curr. next # Calculate the integer representation of the linked list num = 0 curr = head while curr: num = num * 10 + curr.data curr = curr. next # Compare the sum and the integer representation and return the result return num = = sum # Drivers code if __name__ = = '__main__' : # Create a linked list and check if it's an Armstrong number head = Node( 1 ) head. next = Node( 5 ) head. next . next = Node( 3 ) print (isArmstrongNumber(head)) # Output: True |
C#
// C# implementation to check if // Linked List is an Armstrong Number using System; // Define a Node class to represent nodes in the linked list public class Node { public int data; public Node next; public Node( int data) { this .data = data; next = null ; } } public class Program { // Define a function to count the number of digits in the linked list public static int countDigits(Node head) { int count = 0; while (head != null ) { count++; head = head.next; } return count; } // Define a function to check if the linked list is an Armstrong number public static bool isArmstrongNumber(Node head) { // Count the number of digits in the linked list int n = countDigits(head); // Calculate the sum of the digits raised to the power of the number of digits int sum = 0; Node curr = head; while (curr != null ) { sum += ( int )Math.Pow(curr.data, n); curr = curr.next; } // Calculate the integer representation of the linked list int num = 0; curr = head; while (curr != null ) { num = num * 10 + curr.data; curr = curr.next; } // Compare the sum and the integer representation and return the result return num == sum; } public static void Main() { // Create a linked list and check if it's an Armstrong number Node head = new Node(1); head.next = new Node(5); head.next.next = new Node(3); Console.WriteLine(isArmstrongNumber(head)); // Output: True } } |
Javascript
// JavaScript implementation to check if // Linked List is an Armstrong Number // Define a Node class to represent nodes in the linked list class Node { constructor(data) { this .data = data; this .next = null ; } } // Define a function to count the number of digits in the linked list function countDigits(head) { let count = 0; while (head != null ) { count++; head = head.next; } return count; } // Define a function to check if the linked list is an Armstrong number function isArmstrongNumber(head) { // Count the number of digits in the linked list let n = countDigits(head); // Calculate the sum of the digits raised to the power of the number of digits let sum = 0; let curr = head; while (curr != null ) { sum += Math.pow(curr.data, n); curr = curr.next; } // Calculate the integer representation of the linked list let num = 0; curr = head; while (curr != null ) { num = num * 10 + curr.data; curr = curr.next; } // Compare the sum and the integer representation and return the result return num == sum; } // Create a linked list and check if it's an Armstrong number let head = new Node(1); head.next = new Node(5); head.next.next = new Node(3); console.log(isArmstrongNumber(head)); // Output: true |
1
Time Complexity: O(n), where n is the number of nodes in the linked list
Auxiliary Space: O(1)
Related Articles:
Contact Us