Wednesday, 3 July 2013

Smallest Greatest number

Problem Statement

Consider a number 2345. If you multiply its digits then you get the number 120. Now if you again multiply digits of 120 then you will get number 0 which is a one digit number. If I add digitsof 2345 then I will get 14. If I add digits of 14 then I will get 5 which is a one digit number.

Thus any number can be converted into two one digit numbers in some number of steps. You can see 2345 is converted to 0 by using multiplication of digits in 2 steps and it is converted to 5 by using addition of digits in 2 steps. Now consider any number N. Let us say that it can be converted by multiplying digits to a one digit number d1 in n1 steps and by adding digits to one digit number d2 in n2 steps.

Your task is to find smallest number greater than N and less than 1000000000 which can be converted by multiplying its digits to d1 in less than or equal to n1 steps and by adding its digits to d2 in less than or equal to n2 steps.

Input/Output Specs

Input Specification:

Your input will be the number N. (Integer type)


Output Specification:

Output will be the smallest number (integer type) , greater thanN and less than 1000000000 which satisfies the given conditions in the question.

If no such number exists then output “-1” 

Input/Output Specs

Input Specification:

Your input will be the number N. (Integer type)


Output Specification:

Output will be the smallest number (integer type) , greater thanN and less than 1000000000 which satisfies the given conditions in the question.

If no such number exists then output “-1


Examples

Example 1. If N = 2345 then the number 2354 is the smallest number greater than N and less than 1000000000 which satisfies the given conditions.

Example 2. If N = 2895 then the number 2904 is the smallest number greater than N and less than 1000000000 which satisfies the given conditions


Code in c# :

using System;
public class GreatNumber
{
    public static int smallest(int input)
    {   
        GNumber grnumber = new GNumber();
        return grnumber.Find(input);
    }
}


class operation
{
public int steps;
public int result;

    public static bool equals(operation left, operation right)
    {
        bool eq = false;
        if (left.result == right.result && left.steps >= right.steps)
        {
            eq = true;
        }
        return eq;
    }
}

enum Operator
{
Add,
Multiply
}

public class GNumber
{
    int smallnumber = -1;
    int last = 1000000000;
    DateTime start = DateTime.Now;

   
    public int Find(int number)
    {
        if (number < 10)
        return -1;
   
        operation inmulop = null;
        operation inaddop = null;
        Process(number.ToString(), 0, Operator.Multiply, ref inmulop);
        Process(number.ToString(), 0, Operator.Add, ref inaddop);
       
        for (int i = number + 1; i < last; i++)
        {
            string tempnumber = i.ToString();
            if ((DateTime.Now - start).Seconds > 8)
            return -1;
           
            operation mulop = null;
            Process(tempnumber, 0, Operator.Multiply, ref mulop);
            operation addop = null;
            Process(tempnumber, 0, Operator.Add, ref addop);
           
            if (operation.equals(inmulop, mulop) && operation.equals(inaddop, addop))
            {
                smallnumber = i;
                if (i > number)
                break;
            }
        }
        return smallnumber;
       
    }
       
    void Process(string number, int step, Operator oper, ref operation process)
    {
        int result = 0;
        if (Operator.Multiply == oper)
        {
            result = 1;
        }
       
        int length = number.Length;
        if (length > 1)
        {
       
            for (int i = 0; i < number.Length; i++)
            {
                if (oper == Operator.Multiply)
                result = result * int.Parse(number[i].ToString());
                if (oper == Operator.Add)
                result = result + int.Parse(number[i].ToString());
            }
            step++;       
            Process(result.ToString(), step, oper, ref process);
        }
        else
        {
            process = new operation { result = Convert.ToInt32(number), steps = step };
        }   
    }
}





No comments:

Post a Comment