Friday, June 2, 2017

Perfect Number

Problem Statement

We define the Perfect Number is a positive integer that is equal to the sum of all its positive divisors except itself.
Now, given an integer n, write a function that returns true when it is a perfect number and false when it is not.

Link to GitHub :Code

Input: n = 15
Output: false
Divisors of 15 are 1, 3 and 5. Sum of 
divisors is 9 which is not equal to 15.

Input: n = 6
Output: true
Divisors of 6 are 1, 2 and 3. Sum of 
divisors is 6.


A Simple Solution is to go through every number from 1 to n-1 and check if it is a divisor. Maintain sum of all divisors. If sum becomes equal to n, then return true, else return false.

An Efficient Solution is to go through numbers till square root of n. If a number ‘i’ divides n, then add both ‘i’ and n/i to sum.
public class PerfectNumber {
 public static  boolean get(int num)
  //If num is 1 then return false
  if (num==1) return false;
  int sum=0;
  for(int i=2;i<=Math.sqrt(num);i++)
   if(i!=num/i) sum+=num/i;
  return sum == num;


No comments:

Post a Comment