Find all array elements whose digit sum are equal to perfect number
The problem at hand involves finding array elements whose digit sum equals a perfect number. A perfect number is a positive integer that is equal to the sum of its proper divisors, excluding itself. For example, the number 28 is a perfect number because its divisors (excluding itself) are 1, 2, 4, 7, and 14, and their sum is indeed 28.
Given an array of integers, we need to identify and display those elements whose individual digits sum up to a perfect number. This requires breaking down each integer into its digits, summing them up, and then checking if the resulting sum is a perfect number.
Problem Statement
The problem can be broken down into a few key steps:
- Iterate through the array of integers.
- For each integer, calculate the sum of its digits.
- Check if the calculated digit sum is a perfect number.
- If it's a perfect number, display the integer.
Explanation with Example
Let's consider an example to illustrate the problem. We have the following array:
arr = [5, 231, 4, 60, -34, 4888]
.
For each integer in the array, we calculate the digit sum:
5
→ Digit sum: 5231
→ Digit sum: 2 + 3 + 1 = 64
→ Digit sum: 460
→ Digit sum: 6 + 0 = 6-34
→ Ignoring negative integers4888
→ Digit sum: 4 + 8 + 8 + 8 = 28
We observe that the digit sums of 231
and 60
are perfect numbers (6
), and the
digit sum of 4888
is also a perfect number (28
).
Idea to Solve the Problem
To solve this problem, we need to follow these steps:
- Define a function to calculate the digit sum of an integer.
- Define a function to check if a given number is a perfect number.
- Iterate through the array of integers and check if their digit sums are perfect numbers.
Pseudocode
Function digitSum(num):
n = num
result = 0
while n is not 0:
result += n % 10
n = n / 10
return result
Function isPerfectNo(n):
if n < 0:
return false
sum = 0
for i from n/2 down to 1:
if n % i is 0:
sum += i
return sum is n
Function findPerfectNo(arr, n):
result = false
for i from 0 to n - 1:
if arr[i] > 0 and isPerfectNo(digitSum(arr[i])):
print arr[i]
result = true
if result is false:
print "None"
Main:
arr = [5, 231, 4, 60, -34, 4888]
n = length of arr
findPerfectNo(arr, n)
Algorithm Explanation
- The
digitSum
function takes an integer as input and calculates the sum of its digits. - The
isPerfectNo
function checks if a given number is a perfect number by iterating through its divisors. - The
findPerfectNo
function iterates through the array, checks if the digit sum is a perfect number, and prints the result accordingly. - In the
Main
section, we initialize the arrayarr
, find its lengthn
, and call thefindPerfectNo
function.
Code Solution
/*
Java program for
Find all array elements whose digit sum
are equal to perfect number
*/
public class PerfectNumber
{
public int digitSum(int num)
{
int n = num;
int result = 0;
// Calculate digit sum
while (n != 0)
{
// Add last digit
result += (n % 10);
// Remove last digit
n = n / 10;
}
return result;
}
// Check given number is perfect or not
public boolean isPerfectNo(int n)
{
if (n < 0)
{
return false;
}
int sum = 0;
// Calculate sum of divisors of given n
for (int i = (n / 2); i >= 1; i--)
{
if (n % i == 0)
{
sum += i;
}
}
if (sum == n)
{
// When number is perfect number
return true;
}
else
{
return false;
}
}
public void findPerfectNo(int[] arr, int n)
{
boolean result = false;
for (int i = 0; i < n; ++i)
{
if (arr[i] > 0 && isPerfectNo(digitSum(arr[i])))
{
// When array element is perfect number
System.out.print(" " + arr[i]);
// Active result indicator
result = true;
}
}
if (result == false)
{
System.out.print("\n None \n");
}
}
public static void main(String[] args)
{
PerfectNumber task = new PerfectNumber();
int[] arr = {
5 , 231 , 4 , 60 , -34 , 4888
};
int n = arr.length;
/*
arr = [5, 231, 4, 60, -34, 4888]
--------------------------------
2 + 3 + 1 = 6
6 + 0 = 6
4 + 8 + 8 + 8 = 28
Result : [231,60,4888]
*/
task.findPerfectNo(arr, n);
}
}
Output
231 60 4888
/*
C program for
Find all array elements whose digit sum
are equal to perfect number
*/
#include <stdio.h>
int digitSum(int num)
{
int n = num;
int result = 0;
// Calculate digit sum
while (n != 0)
{
// Add last digit
result += (n % 10);
// Remove last digit
n = n / 10;
}
return result;
}
// Check given number is perfect or not
int isPerfectNo(int n)
{
if (n < 0)
{
return 0;
}
int sum = 0;
// Calculate sum of divisors of given n
for (int i = (n / 2); i >= 1; i--)
{
if (n % i == 0)
{
sum += i;
}
}
if (sum == n)
{
// When number is perfect number
return 1;
}
else
{
return 0;
}
}
void findPerfectNo(int arr[], int n)
{
int result = 0;
for (int i = 0; i < n; ++i)
{
if (arr[i] > 0 && isPerfectNo(digitSum(arr[i])))
{
// When array element is perfect number
printf(" %d", arr[i]);
// Active result indicator
result = 1;
}
}
if (result == 0)
{
printf("\n None \n");
}
}
int main(int argc, char const *argv[])
{
int arr[] =
{
5 , 231 , 4 , 60 , -34 , 4888
};
int n = sizeof(arr) / sizeof(arr[0]);
/*
arr = [5, 231, 4, 60, -34, 4888]
--------------------------------
2 + 3 + 1 = 6
6 + 0 = 6
4 + 8 + 8 + 8 = 28
Result : [231,60,4888]
*/
findPerfectNo(arr, n);
return 0;
}
Output
231 60 4888
// Include header file
#include <iostream>
using namespace std;
/*
C++ program for
Find all array elements whose digit sum
are equal to perfect number
*/
class PerfectNumber
{
public: int digitSum(int num)
{
int n = num;
int result = 0;
// Calculate digit sum
while (n != 0)
{
// Add last digit
result += (n % 10);
// Remove last digit
n = n / 10;
}
return result;
}
// Check given number is perfect or not
bool isPerfectNo(int n)
{
if (n < 0)
{
return false;
}
int sum = 0;
// Calculate sum of divisors of given n
for (int i = (n / 2); i >= 1; i--)
{
if (n % i == 0)
{
sum += i;
}
}
if (sum == n)
{
// When number is perfect number
return true;
}
else
{
return false;
}
}
void findPerfectNo(int arr[], int n)
{
bool result = false;
for (int i = 0; i < n; ++i)
{
if (arr[i] > 0 &&
this->isPerfectNo(this->digitSum(arr[i])))
{
// When array element is perfect number
cout << " " << arr[i];
// Active result indicator
result = true;
}
}
if (result == false)
{
cout << "\n None \n";
}
}
};
int main()
{
PerfectNumber *task = new PerfectNumber();
int arr[] = {
5 , 231 , 4 , 60 , -34 , 4888
};
int n = sizeof(arr) / sizeof(arr[0]);
/*
arr = [5, 231, 4, 60, -34, 4888]
--------------------------------
2 + 3 + 1 = 6
6 + 0 = 6
4 + 8 + 8 + 8 = 28
Result : [231,60,4888]
*/
task->findPerfectNo(arr, n);
return 0;
}
Output
231 60 4888
// Include namespace system
using System;
/*
Csharp program for
Find all array elements whose digit sum
are equal to perfect number
*/
public class PerfectNumber
{
public int digitSum(int num)
{
int n = num;
int result = 0;
// Calculate digit sum
while (n != 0)
{
// Add last digit
result += (n % 10);
// Remove last digit
n = n / 10;
}
return result;
}
// Check given number is perfect or not
public Boolean isPerfectNo(int n)
{
if (n < 0)
{
return false;
}
int sum = 0;
// Calculate sum of divisors of given n
for (int i = (n / 2); i >= 1; i--)
{
if (n % i == 0)
{
sum += i;
}
}
if (sum == n)
{
// When number is perfect number
return true;
}
else
{
return false;
}
}
public void findPerfectNo(int[] arr, int n)
{
Boolean result = false;
for (int i = 0; i < n; ++i)
{
if (arr[i] > 0 &&
this.isPerfectNo(this.digitSum(arr[i])))
{
// When array element is perfect number
Console.Write(" " + arr[i]);
// Active result indicator
result = true;
}
}
if (result == false)
{
Console.Write("\n None \n");
}
}
public static void Main(String[] args)
{
PerfectNumber task = new PerfectNumber();
int[] arr = {
5 , 231 , 4 , 60 , -34 , 4888
};
int n = arr.Length;
/*
arr = [5, 231, 4, 60, -34, 4888]
--------------------------------
2 + 3 + 1 = 6
6 + 0 = 6
4 + 8 + 8 + 8 = 28
Result : [231,60,4888]
*/
task.findPerfectNo(arr, n);
}
}
Output
231 60 4888
package main
import "fmt"
/*
Go program for
Find all array elements whose digit sum
are equal to perfect number
*/
func digitSum(num int) int {
var n int = num
var result int = 0
// Calculate digit sum
for (n != 0) {
// Add last digit
result += (n % 10)
// Remove last digit
n = n / 10
}
return result
}
// Check given number is perfect or not
func isPerfectNo(n int) bool {
if n < 0 {
return false
}
var sum int = 0
// Calculate sum of divisors of given n
for i :=(n / 2) ; i >= 1 ; i-- {
if n % i == 0 {
sum += i
}
}
if sum == n {
// When number is perfect number
return true
} else {
return false
}
}
func findPerfectNo(arr[] int, n int) {
var result bool = false
for i := 0 ; i < n ; i++ {
if arr[i] > 0 &&
isPerfectNo(digitSum(arr[i])) {
// When array element is perfect number
fmt.Print(" ", arr[i])
// Active result indicator
result = true
}
}
if result == false {
fmt.Print("\n None \n")
}
}
func main() {
var arr = [] int { 5 , 231 , 4 , 60 , - 34 , 4888}
var n int = len(arr)
/*
arr = [5, 231, 4, 60, -34, 4888]
--------------------------------
2 + 3 + 1 = 6
6 + 0 = 6
4 + 8 + 8 + 8 = 28
Result : [231,60,4888]
*/
findPerfectNo(arr, n)
}
Output
231 60 4888
<?php
/*
Php program for
Find all array elements whose digit sum
are equal to perfect number
*/
class PerfectNumber
{
public function digitSum($num)
{
$n = $num;
$result = 0;
// Calculate digit sum
while ($n != 0)
{
// Add last digit
$result += ($n % 10);
// Remove last digit
$n = (int)($n / 10);
}
return $result;
}
// Check given number is perfect or not
public function isPerfectNo($n)
{
if ($n < 0)
{
return false;
}
$sum = 0;
// Calculate sum of divisors of given n
for ($i = ((int)($n / 2)); $i >= 1; $i--)
{
if ($n % $i == 0)
{
$sum += $i;
}
}
if ($sum == $n)
{
// When number is perfect number
return true;
}
else
{
return false;
}
}
public function findPerfectNo($arr, $n)
{
$result = false;
for ($i = 0; $i < $n; ++$i)
{
if ($arr[$i] > 0 &&
$this->isPerfectNo($this->digitSum($arr[$i])))
{
// When array element is perfect number
echo(" ".$arr[$i]);
// Active result indicator
$result = true;
}
}
if ($result == false)
{
echo("\n None \n");
}
}
}
function main()
{
$task = new PerfectNumber();
$arr = array(5, 231, 4, 60, -34, 4888);
$n = count($arr);
/*
arr = [5, 231, 4, 60, -34, 4888]
--------------------------------
2 + 3 + 1 = 6
6 + 0 = 6
4 + 8 + 8 + 8 = 28
Result : [231,60,4888]
*/
$task->findPerfectNo($arr, $n);
}
main();
Output
231 60 4888
/*
Node JS program for
Find all array elements whose digit sum
are equal to perfect number
*/
class PerfectNumber
{
digitSum(num)
{
var n = num;
var result = 0;
// Calculate digit sum
while (n != 0)
{
// Add last digit
result += (n % 10);
// Remove last digit
n = parseInt(n / 10);
}
return result;
}
// Check given number is perfect or not
isPerfectNo(n)
{
if (n < 0)
{
return false;
}
var sum = 0;
// Calculate sum of divisors of given n
for (var i = (parseInt(n / 2)); i >= 1; i--)
{
if (n % i == 0)
{
sum += i;
}
}
if (sum == n)
{
// When number is perfect number
return true;
}
else
{
return false;
}
}
findPerfectNo(arr, n)
{
var result = false;
for (var i = 0; i < n; ++i)
{
if (arr[i] > 0 &&
this.isPerfectNo(this.digitSum(arr[i])))
{
// When array element is perfect number
process.stdout.write(" " + arr[i]);
// Active result indicator
result = true;
}
}
if (result == false)
{
process.stdout.write("\n None \n");
}
}
}
function main()
{
var task = new PerfectNumber();
var arr = [5, 231, 4, 60, -34, 4888];
var n = arr.length;
/*
arr = [5, 231, 4, 60, -34, 4888]
--------------------------------
2 + 3 + 1 = 6
6 + 0 = 6
4 + 8 + 8 + 8 = 28
Result : [231,60,4888]
*/
task.findPerfectNo(arr, n);
}
main();
Output
231 60 4888
# Python 3 program for
# Find all array elements whose digit sum
# are equal to perfect number
class PerfectNumber :
def digitSum(self, num) :
n = num
result = 0
# Calculate digit sum
while (n != 0) :
# Add last digit
result += (n % 10)
# Remove last digit
n = int(n / 10)
return result
# Check given number is perfect or not
def isPerfectNo(self, n) :
if (n < 0) :
return False
sum = 0
i = (int(n / 2))
# Calculate sum of divisors of given n
while (i >= 1) :
if (n % i == 0) :
sum += i
i -= 1
if (sum == n) :
# When number is perfect number
return True
else :
return False
def findPerfectNo(self, arr, n) :
result = False
i = 0
while (i < n) :
if (arr[i] > 0 and self.isPerfectNo(self.digitSum(arr[i]))) :
# When list element is perfect number
print(" ", arr[i], end = "")
# Active result indicator
result = True
i += 1
if (result == False) :
print("\n None ")
def main() :
task = PerfectNumber()
arr = [5, 231, 4, 60, -34, 4888]
n = len(arr)
# arr = [5, 231, 4, 60, -34, 4888]
# --------------------------------
# 2 + 3 + 1 = 6
# 6 + 0 = 6
# 4 + 8 + 8 + 8 = 28
# Result : [231,60,4888]
task.findPerfectNo(arr, n)
if __name__ == "__main__": main()
Output
231 60 4888
# Ruby program for
# Find all array elements whose digit sum
# are equal to perfect number
class PerfectNumber
def digitSum(num)
n = num
result = 0
# Calculate digit sum
while (n != 0)
# Add last digit
result += (n % 10)
# Remove last digit
n = n / 10
end
return result
end
# Check given number is perfect or not
def isPerfectNo(n)
if (n < 0)
return false
end
sum = 0
i = (n / 2)
# Calculate sum of divisors of given n
while (i >= 1)
if (n % i == 0)
sum += i
end
i -= 1
end
if (sum == n)
# When number is perfect number
return true
else
return false
end
end
def findPerfectNo(arr, n)
result = false
i = 0
while (i < n)
if (arr[i] > 0 && self.isPerfectNo(self.digitSum(arr[i])))
# When array element is perfect number
print(" ", arr[i])
# Active result indicator
result = true
end
i += 1
end
if (result == false)
print("\n None \n")
end
end
end
def main()
task = PerfectNumber.new()
arr = [5, 231, 4, 60, -34, 4888]
n = arr.length
# arr = [5, 231, 4, 60, -34, 4888]
# --------------------------------
# 2 + 3 + 1 = 6
# 6 + 0 = 6
# 4 + 8 + 8 + 8 = 28
# Result : [231,60,4888]
task.findPerfectNo(arr, n)
end
main()
Output
231 60 4888
/*
Scala program for
Find all array elements whose digit sum
are equal to perfect number
*/
class PerfectNumber()
{
def digitSum(num: Int): Int = {
var n: Int = num;
var result: Int = 0;
// Calculate digit sum
while (n != 0)
{
// Add last digit
result += (n % 10);
// Remove last digit
n = n / 10;
}
return result;
}
// Check given number is perfect or not
def isPerfectNo(n: Int): Boolean = {
if (n < 0)
{
return false;
}
var sum: Int = 0;
var i: Int = (n / 2);
// Calculate sum of divisors of given n
while (i >= 1)
{
if (n % i == 0)
{
sum += i;
}
i -= 1;
}
if (sum == n)
{
// When number is perfect number
return true;
}
else
{
return false;
}
}
def findPerfectNo(arr: Array[Int], n: Int): Unit = {
var result: Boolean = false;
var i: Int = 0;
while (i < n)
{
if (arr(i) > 0 && isPerfectNo(digitSum(arr(i))))
{
// When array element is perfect number
print(" " + arr(i));
// Active result indicator
result = true;
}
i += 1;
}
if (result == false)
{
print("\n None \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: PerfectNumber = new PerfectNumber();
var arr: Array[Int] = Array(5, 231, 4, 60, -34, 4888);
var n: Int = arr.length;
/*
arr = [5, 231, 4, 60, -34, 4888]
--------------------------------
2 + 3 + 1 = 6
6 + 0 = 6
4 + 8 + 8 + 8 = 28
Result : [231,60,4888]
*/
task.findPerfectNo(arr, n);
}
}
Output
231 60 4888
import Foundation;
/*
Swift 4 program for
Find all array elements whose digit sum
are equal to perfect number
*/
class PerfectNumber
{
func digitSum(_ num: Int) -> Int
{
var n: Int = num;
var result: Int = 0;
// Calculate digit sum
while (n != 0)
{
// Add last digit
result += (n % 10);
// Remove last digit
n = n / 10;
}
return result;
}
// Check given number is perfect or not
func isPerfectNo(_ n: Int) -> Bool
{
if (n < 0)
{
return false;
}
var sum: Int = 0;
var i: Int = (n / 2);
// Calculate sum of divisors of given n
while (i >= 1)
{
if (n % i == 0)
{
sum += i;
}
i -= 1;
}
if (sum == n)
{
// When number is perfect number
return true;
}
else
{
return false;
}
}
func findPerfectNo(_ arr: [Int], _ n: Int)
{
var result: Bool = false;
var i: Int = 0;
while (i < n)
{
if (arr[i] > 0 && self.isPerfectNo(self.digitSum(arr[i])))
{
// When array element is perfect number
print(" ", arr[i], terminator: "");
// Active result indicator
result = true;
}
i += 1;
}
if (result == false)
{
print("\n None ");
}
}
}
func main()
{
let task: PerfectNumber = PerfectNumber();
let arr: [Int] = [5, 231, 4, 60, -34, 4888];
let n: Int = arr.count;
/*
arr = [5, 231, 4, 60, -34, 4888]
--------------------------------
2 + 3 + 1 = 6
6 + 0 = 6
4 + 8 + 8 + 8 = 28
Result : [231,60,4888]
*/
task.findPerfectNo(arr, n);
}
main();
Output
231 60 4888
/*
Kotlin program for
Find all array elements whose digit sum
are equal to perfect number
*/
class PerfectNumber
{
fun digitSum(num: Int): Int
{
var n: Int = num;
var result: Int = 0;
// Calculate digit sum
while (n != 0)
{
// Add last digit
result += (n % 10);
// Remove last digit
n = n / 10;
}
return result;
}
// Check given number is perfect or not
fun isPerfectNo(n: Int): Boolean
{
if (n < 0)
{
return false;
}
var sum: Int = 0;
var i: Int = (n / 2);
// Calculate sum of divisors of given n
while (i >= 1)
{
if (n % i == 0)
{
sum += i;
}
i -= 1;
}
if (sum == n)
{
// When number is perfect number
return true;
}
else
{
return false;
}
}
fun findPerfectNo(arr: Array < Int > , n: Int): Unit
{
var result: Boolean = false;
var i: Int = 0;
while (i < n)
{
if (arr[i] > 0 && this.isPerfectNo(this.digitSum(arr[i])))
{
// When array element is perfect number
print(" " + arr[i]);
// Active result indicator
result = true;
}
i += 1;
}
if (result == false)
{
print("\n None \n");
}
}
}
fun main(args: Array < String > ): Unit
{
val task: PerfectNumber = PerfectNumber();
val arr: Array < Int > = arrayOf(5, 231, 4, 60, -34, 4888);
val n: Int = arr.count();
/*
arr = [5, 231, 4, 60, -34, 4888]
--------------------------------
2 + 3 + 1 = 6
6 + 0 = 6
4 + 8 + 8 + 8 = 28
Result : [231,60,4888]
*/
task.findPerfectNo(arr, n);
}
Output
231 60 4888
Time Complexity Analysis
- The
digitSum
function has a time complexity of O(log n), where n is the input number, as it involves dividing the number by 10 in each iteration of the loop. - The
isPerfectNo
function has a time complexity of O(n), where n is the input number, as it involves iterating through the divisors up to n/2. - The
findPerfectNo
function has a time complexity of O(m * (log n + n/2)), where m is the number of elements in the array and n is the maximum value among the array elements. This is because it calls bothdigitSum
andisPerfectNo
functions for each array element. - Thus, the overall time complexity of the given code is dominated by the
findPerfectNo
function, which is O(m * (log n + n/2)).
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment