CREATE OWN LIBRARY

Happy Numbers between a range

Back to Programming

Description

Before seeing this program please follow check Happy Number

A number is said to be a happy number if the number reaches 1 after a number of steps and in each step, the sum of the squares of the digits are calculated and the number is replaced with the sum and again the same step is repeated till it reaches 1.

 

For example, let us consider the number 82.

82+22=64+4=68

62+82=36+64=100

12+02+02=1

Therefore, it is a happy number.

Here we find the number of Happy Numbers between a range

Algorithm

INPUT: The ranges
OUTPUT: The happy numbers between the ranges
PROCESS:
Step 1: [Taking the inputs]
	Read p, q [the ranges]
Step 2: [Finding the Happy Number]
	For i=p to q repeat
		Set n<-i
Set sum<-0
		[Checking for happy number]
		While sum≠1 and sum≠4 repeat
   			Set sum<-0
   			While n>0 repeat
    				Set r<-n mod 10
    				Set sum<-sum+(r×r)
    				Set n<-n/10 
  			[End of ‘while’ loop]
  			Set n<-sum
  		[End of ‘while’ loop]
  		[Printing the result]
  		If sum=1 
 			Print i
		[End of ‘if’]
	[End of ‘for’ loop]		
Step 3: Stop.

Code

Time Complexity:

for(i=p;i<=q;i++)--------------------------------O(k)

                {               sum=0;

                                n=i;

                                //checking for happy number

                                while(sum!=1 && sum!=4)---------O(m)

                                {

                                               sum=0;

                                                while(n>0)---------------------O(log10n)

                                                {

                                                r=n%10;

                                                sum+=(r*r);

                                                n=n/10;

                                                }

                                                n=sum;

                                }

                                //printing the result

                                if(sum==1)

                                                printf("%d ",i);

                }

The time complexity of this program is O(k*m*log10n) where ‘k’ is the number between the ranges, for each number ‘m’ is the number of elements before reaching 1 of which the sum of the square of the digits are to be calculated and ‘n’ is each number that is checked.

 

Space Complexity:

The space complexity of this program is O(1) as it requires a constant number of memory spaces for any given input.