Hey ppl,
I was browsing thro the topcoder sample problems and came up with this one. Plz suggest some good algorithm for this.

Problem Statement
Note: Please keep programs under 7000 characters in length. Thank you

Class Name: SquareDigits
Method Name: smallestResult
Parameters: int
Returns: int

Define the function S(x) as the sum of the squares of the digits of x.
For example: S(3)=3*3=9 and S(230)=2*2+3*3+0*0=13.

Define the set T(x) to be the set of unique numbers that are produced by
repeatedly applying S to x. That is: S(x), S(S(x)), S(S(S(x))), etc...
For example, repeatedly applying S to 37:

S(37)=3*3+7*7=58.  
S(58)=5*5+8*8=89.
S(89)=145.
S(145)=42. 
S(42)=20.
S(20)=4.
S(4)=16.
S(16)=37. 

Note this sequence will repeat so we can stop calculating now and:

T(37)={58,89,145,42,20,4,16,37}.

However, note T(x) may not necessarily contain x.

Implement a class SquareDigits, which contains a method smallestResult. The
method takes an int, n, as a parameter and returns the smallest int, x, such
that T(x) contains n.

The method signature is (be sure your method is public):

int smallestResult(int n); 

TopCoder will ensure n is non-negative and is between 0 and 199 inclusive.

Examples:

If n=0: S(0) = 0, so T(0)={0}, so the method should return 0.

If n=2: T(0) through T(10) do not contain the value 2.  If x=11, however:
S(11)=1*1+1*1=2, so T(11) contains 2, and the method should return 11.

If n=10: T(0) through T(6) do not contain 10.  If x=7:
S(7)=49.
S(49)=97.
S(97)=130.
S(130)=10.
S(10)=1.
and it starts to repeat... 
so T(7) is {49,97,130,10,1}, which contains 10, and the method should return 7.

n=1 -> x=1 
n=19 -> x=133
n=85 -> x=5
n=112 -> x=2666

Definition
Class:              SquareDigits
Method:         smallestResult
Parameters:         int
Returns:            int
Method signature:       int smallestResult(int param0)
 (be sure your method is public)

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Edited 3 Years Ago by mike_2000_17: Fixed formatting

How about you suggest a bad algorithm, or maybe even a half decent algorithm first?

Because this to me is just another homework dump with a whopping ZERO PERCENT EFFORT ON YOUR PART

Sorry, forgot to mention the algorithm i had in mind. I can proceed till generating the T(X) set by seperating the digits. Iam unsure about how to proceed further without wasting memory/creating shortage of memory by allocating random array size for storing the set T(X).

My idea:

1) Get the no as input along with the no of digits

2) Separate the digits by collecting remainders of division by 10.

3) Use the digits, perform the function S(X).

I need help from this point. I need to know how to efficiently calculate the T(X) set without wasting memory/ with shortage of memory. And then how to proceed in finding X?

dear friend , I really can finish this for you . But that really not help you for this assignment . what you need is the knowledge isn't that ?

so lets dig into the problem , may be this is where you stucked . I can give you a good idea how to decompose digits for a example , you can write ,
312 = 3 * 100 + 1* 10 + 2
so like that , you can use the / and the modulo operators to get , like this
312 / 100 = 3
312 %100 = 12

then do this to the 12 , again there you goes
12 / 10 = 1
12 % 10 = 2
then do this again for the 2
2 / 1 = 2
2 % 1 = 0
so you can create a while loop until , you reach the % thing to the zero .
so then simply you can write a program for adding them and getting your results .


dear friend I really different from others , but I if I did this , it really hurts back to you .

any problem that you stuck during developing this algrothym pls ask . someone will help you .
-- best regards

@sanzilla

You are right. I don't need just answers. I figured out till extracting digits. I want info on how to proceed further. I can create a very large array to store the set T(X) which results from the function S(X). But there is a possibility that the array size i've declared may not be sufficient and it may be too large also. I want a suggestion to overcome this.

so array size is the problem ,

array is a static memory allocation method , you have to choose a dynamic memory allocation method .

so use those other data structures like Vector , stack or a link list . C++ STL have these things already . Go ahead and use these things.
(C++ STL means standard library for the c++ , no matter what compiler that you using there are still there).
I recommand you to use Vector data structure instead of a Array.There are many alternatives than using a array.

I guess this could help also... i don't know how really clever this is but why not use all the nice stuff STL gives? for example you could use a set structure to check when the cyclic array of numbers starts to repeat by inserting results into it and checking if the size of the set has changed...

@Sanzilla

Thanks man. Im not aware of Vector concept in STL. Any links that can help me?

@gregorynoob

Will the concept work well if the number that repeats isn't in the starting position of the circular array? I dunno much about this cyclic array. Is it similar to Circular Linked List?

You don't need an array at all. Your idea

1) Get the no as input along with the no of digits

2) Separate the digits by collecting remainders of division by 10.

3) Use the digits, perform the function S(X).

is close. All you need for #1 is to get the value.
For number 2 & 3, get one digit by collecting the remainder, perform S(X) on that digit. Repeat until the original number is 0 and you're done.

@Waltp

I don't need an array for this, but i need it for the next step. Plz see my first post. It has the complete statement.

This article has been dead for over six months. Start a new discussion instead.