Question

Given a positive integer n, write a recursive algorithm that returns the number of the digits in n. For example, if the given number n is 12345, the algorithm should return 5. What is the time complexity of your algorithm? use java

Answer 1

1. Take input from user and store it in a variable "num"
2. Check whether value of num is valid i.e integer and positive
3. if value is not valid repeat step 1 and 2 until user enter valid value
4. if value is valid call recursive function with parameter as "num" do step 5 and 6
5. check if value is 0, if 0 return 0
6. else increase counter by 1 and go to step 4 and make num=num/10

import java.io.*; 
import java.util.Scanner;

class Main 
{ 
    public static int count=0;// to count number of digits
    // method to calculate digits in a number
    // It will check whether n=0 or not
    // if n=0 it will terminate
    // else if will call itself with n/10 and count will be increased by 1
    static int digits(int n) 
    {  
        if (n == 0) 
            return 0; 
        count++;
        return (digits(n / 10)); 
    } 
    // main function
    public static void main(String args[]) 
    { 
        int num=0;// to store user entered value
        boolean invalid=true; // to check whether value entered by user is valid or not
        do
        {
            try
            {
                Scanner sc = new Scanner(System.in);
                // range of int is from 2,147,483,648 to 2,147,483,647 i.e upto 10 digits
                // if we try to enter more than 10 digits it will throw an exception 
                // we can change this limit by using other data types in place of int
                System.out.println("Enter positive integer upto 10 digits");
                num=sc.nextInt();
                // if num is positive it will be accepted else user will be prompted to enter number once again
                if(num>=0) 
                {
                    invalid=false;
                }
                else 
                {
                    invalid=true;
                }
            }
            // exception will be thrown if user tries to enter any value other than integer
            // i.e string value , char value, value greater than range of integer etc.
            catch(Exception e)
            {
                invalid=true;
            }
        }while(invalid);
        // call to digit function with user entered value
        if(num==0)
        {
            System.out.println("digits in " +  num + " is 1");   
        }
        else
        {
            int result = digits(num); 
            System.out.println("digits in " +  num + " is " + count); 
        }
        
    } 
}

If we consider digits in number =d
then our complexity becomes O(d) because function will be called d+1 times that will evaluated to d
therefore complexity=O(d)