Techno Blender
Digitally Yours.


Technology

Check if a Linked List is an Armstrong Number

By Ann Roberts
0 25


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 = 153

Input: 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++

  

#include <bits/stdc++.h>

using namespace std;

  

class Node {

public:

    int data;

    Node* next;

    Node(int data)

    {

        this->data = data;

        next = NULL;

    }

};

  

string listToString(Node* head)

{

    string result = "";

    Node* curr = head;

    while (curr != NULL) {

        result += to_string(curr->data);

        curr = curr->next;

    }

    return result;

}

  

bool isArmstrongNumber(Node* head)

{

  

    

    

    string str = listToString(head);

  

    

    

    int n = str.length();

  

    

    

    

    int sum = 0;

    for (int i = 0; i < n; i++) {

        int digit = str[i] - '0';

        sum += pow(digit, n);

    }

  

    

    

    int num = stoi(str);

  

    

    

    return num == sum;

}

  

int main()

{

  

    

    

    Node* head = new Node(1);

    head->next = new Node(5);

    head->next->next = new Node(3);

    cout << isArmstrongNumber(head)

         << endl;

  

    return 0;

}

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)
  • 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++

  

#include <bits/stdc++.h>

using namespace std;

  

class Node {

public:

    int data;

    Node* next;

    Node(int data)

    {

        this->data = data;

        next = NULL;

    }

};

  

int countDigits(Node* head)

{

    int count = 0;

    while (head != NULL) {

        count++;

        head = head->next;

    }

    return count;

}

  

bool isArmstrongNumber(Node* head)

{

  

    

    

    int n = countDigits(head);

  

    

    

    

    int sum = 0;

    Node* curr = head;

    while (curr != NULL) {

        sum += pow(curr->data, n);

        curr = curr->next;

    }

  

    

    

    int num = 0;

    curr = head;

    while (curr != NULL) {

        num = num * 10 + curr->data;

        curr = curr->next;

    }

  

    

    

    return num == sum;

}

  

int main()

{

  

    

    

    Node* head = new Node(1);

    head->next = new Node(5);

    head->next->next = new Node(3);

    cout << isArmstrongNumber(head)

         << endl;

  

    return 0;

}

Javascript

  

class Node {

    constructor(data) {

    this.data = data;

    this.next = null;

    }

}

  

function countDigits(head) {

    let count = 0;

    while (head != null) {

        count++;

        head = head.next;

    }

    return count;

}

  

function isArmstrongNumber(head) {

    

    let n = countDigits(head);

      

    

    let sum = 0;

    let curr = head;

    while (curr != null) {

        sum += Math.pow(curr.data, n);

        curr = curr.next;

    }

  

    

    let num = 0;

    curr = head;

    while (curr != null) {

        num = num * 10 + curr.data;

        curr = curr.next;

    }

  

    

    return num == sum;

}

  

let head = new Node(1);

head.next = new Node(5);

head.next.next = new Node(3);

console.log(isArmstrongNumber(head));

C#

  

using System;

  

public class Node {

    public int data;

    public Node next;

    public Node(int data)

    {

        this.data = data;

        next = null;

    }

}

  

public class Program {

    

    public static int countDigits(Node head)

    {

        int count = 0;

        while (head != null) {

            count++;

            head = head.next;

        }

        return count;

    }

    

    public static bool isArmstrongNumber(Node head)

    {

        

        int n = countDigits(head);

  

        

        int sum = 0;

        Node curr = head;

        while (curr != null) {

            sum += (int)Math.Pow(curr.data, n);

            curr = curr.next;

        }

  

        

        int num = 0;

        curr = head;

        while (curr != null) {

            num = num * 10 + curr.data;

            curr = curr.next;

        }

  

        

        return num == sum;

    }

  

    public static void Main()

    {

        

        Node head = new Node(1);

        head.next = new Node(5);

        head.next.next = new Node(3);

  

        Console.WriteLine(isArmstrongNumber(head));

    }

}

Time Complexity: O(n), where n is the number of nodes in the linked list
Auxiliary Space: O(1)

Related Articles:


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 = 153

Input: 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++

  

#include <bits/stdc++.h>

using namespace std;

  

class Node {

public:

    int data;

    Node* next;

    Node(int data)

    {

        this->data = data;

        next = NULL;

    }

};

  

string listToString(Node* head)

{

    string result = "";

    Node* curr = head;

    while (curr != NULL) {

        result += to_string(curr->data);

        curr = curr->next;

    }

    return result;

}

  

bool isArmstrongNumber(Node* head)

{

  

    

    

    string str = listToString(head);

  

    

    

    int n = str.length();

  

    

    

    

    int sum = 0;

    for (int i = 0; i < n; i++) {

        int digit = str[i] - '0';

        sum += pow(digit, n);

    }

  

    

    

    int num = stoi(str);

  

    

    

    return num == sum;

}

  

int main()

{

  

    

    

    Node* head = new Node(1);

    head->next = new Node(5);

    head->next->next = new Node(3);

    cout << isArmstrongNumber(head)

         << endl;

  

    return 0;

}

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)
  • 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++

  

#include <bits/stdc++.h>

using namespace std;

  

class Node {

public:

    int data;

    Node* next;

    Node(int data)

    {

        this->data = data;

        next = NULL;

    }

};

  

int countDigits(Node* head)

{

    int count = 0;

    while (head != NULL) {

        count++;

        head = head->next;

    }

    return count;

}

  

bool isArmstrongNumber(Node* head)

{

  

    

    

    int n = countDigits(head);

  

    

    

    

    int sum = 0;

    Node* curr = head;

    while (curr != NULL) {

        sum += pow(curr->data, n);

        curr = curr->next;

    }

  

    

    

    int num = 0;

    curr = head;

    while (curr != NULL) {

        num = num * 10 + curr->data;

        curr = curr->next;

    }

  

    

    

    return num == sum;

}

  

int main()

{

  

    

    

    Node* head = new Node(1);

    head->next = new Node(5);

    head->next->next = new Node(3);

    cout << isArmstrongNumber(head)

         << endl;

  

    return 0;

}

Javascript

  

class Node {

    constructor(data) {

    this.data = data;

    this.next = null;

    }

}

  

function countDigits(head) {

    let count = 0;

    while (head != null) {

        count++;

        head = head.next;

    }

    return count;

}

  

function isArmstrongNumber(head) {

    

    let n = countDigits(head);

      

    

    let sum = 0;

    let curr = head;

    while (curr != null) {

        sum += Math.pow(curr.data, n);

        curr = curr.next;

    }

  

    

    let num = 0;

    curr = head;

    while (curr != null) {

        num = num * 10 + curr.data;

        curr = curr.next;

    }

  

    

    return num == sum;

}

  

let head = new Node(1);

head.next = new Node(5);

head.next.next = new Node(3);

console.log(isArmstrongNumber(head));

C#

  

using System;

  

public class Node {

    public int data;

    public Node next;

    public Node(int data)

    {

        this.data = data;

        next = null;

    }

}

  

public class Program {

    

    public static int countDigits(Node head)

    {

        int count = 0;

        while (head != null) {

            count++;

            head = head.next;

        }

        return count;

    }

    

    public static bool isArmstrongNumber(Node head)

    {

        

        int n = countDigits(head);

  

        

        int sum = 0;

        Node curr = head;

        while (curr != null) {

            sum += (int)Math.Pow(curr.data, n);

            curr = curr.next;

        }

  

        

        int num = 0;

        curr = head;

        while (curr != null) {

            num = num * 10 + curr.data;

            curr = curr.next;

        }

  

        

        return num == sum;

    }

  

    public static void Main()

    {

        

        Node head = new Node(1);

        head.next = new Node(5);

        head.next.next = new Node(3);

  

        Console.WriteLine(isArmstrongNumber(head));

    }

}

Time Complexity: O(n), where n is the number of nodes in the linked list
Auxiliary Space: O(1)

Related Articles:

FOLLOW US ON GOOGLE NEWS

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.
Ann Roberts 41603 posts 0 comments
Leave a comment
More Stories

M1 Mac and newer have an unpatchable vulnerability

5 Things about AI you may have missed today: GenAI to…

How the EU’s antitrust lawsuit against tech giant…

1 of 13,869