4

So my friend asked me this question as interview practice: Using Objective-C & Foundation Kit, Write a method that takes a single digit int, and logs out to the console the precise result of that int being raised to the power of 100.

Initially I thought it sounded easy, but then I realized that even a single digit number raised to the power of 100 would quickly come close to 100 digits, which would overflow.

So I tried tackling this problem by creating an NSArray w/ NSNumbers (for reflection), where each object in the array is a place in the final result number. Then I perform the multiplication math (including factoring in carries), and then print out a string formed by concatenating the objects in the array. Here is my implementation w/ input 3:

   NSNumber *firstNum = [NSNumber numberWithInteger:3];
   NSMutableArray *numArray = [NSMutableArray arrayWithArray:@[firstNum]];
   for( int i=0; i<99; i++)
   {
      int previousCarry = 0;
      for( int j=0; j<[numArray count]; j++)
      {
         int newInt = [firstNum intValue] * [[numArray objectAtIndex:j] intValue] + previousCarry;
         NSNumber *calculation = [NSNumber numberWithInteger:newInt];
         previousCarry = [calculation intValue]/10;
         NSNumber *newValue = [NSNumber numberWithInteger:(newInt % 10)];
         [numArray replaceObjectAtIndex:j withObject:newValue];

      }
      if(previousCarry > 0)
      {
         [numArray addObject:[NSNumber numberWithInteger:previousCarry]];
      }
   }

   NSArray* reversedArray = [[numArray reverseObjectEnumerator] allObjects];

   NSString *finalNumber = [reversedArray componentsJoinedByString:@""];
   NSLog(@"%@", finalNumber);

This isn't a problem out of a textbook or anything so I don't have any reference to double check my work. How does this solution sound to you guys? I'm a little worried that it's pretty naive even though the complexity is O(N), I can't help but feel like I'm not utilizing a type/class or method unique to Objective-C or Foundation Kit that would maybe produce a more optimal solution-- or at the very least make the algorithm cleaner and look more impressive

A O
  • 5,516
  • 3
  • 33
  • 68
  • Why are you using `NSNumber`? – trojanfoe May 01 '15 at 06:52
  • Good question, so I think because initially I was using fast enumeration to iterate through the array, and then modifying the current object to update it with the new value. That was before I knew `[numArray replaceObjectAtIndex:j withObject:newValue];` existed. I guess I'm also still shakey on the different between the primitive type `int` and the `NSNumber`. I thought that `int` is not an object and therefore I couldn't int element in an array because i can't have a reference to a primitive type. – A O May 01 '15 at 07:08
  • It's the kind of problem where plain old C is a lot, lot easier. To use an array of 100 ints: int myarray [100]; that's it. – gnasher729 May 01 '15 at 07:22
  • Try a bignum library? – Schemetrical May 01 '15 at 08:53

2 Answers2

3

Write a method that takes a single digit int, and logs out to the console the precise result of that int being raised to the power of 100.

That strikes me as a typical interview "trick"[*] question - "single digit", "logs out to console"...

Here goes:

NSString *singleDigitTo100(int d)
{
   static NSString *powers[] =
   {
      @"0",
      @"1",
      @"1267650600228229401496703205376",
      @"515377520732011331036461129765621272702107522001",
      @"1606938044258990275541962092341162602522202993782792835301376",
      @"7888609052210118054117285652827862296732064351090230047702789306640625",
      @"653318623500070906096690267158057820537143710472954871543071966369497141477376",
      @"3234476509624757991344647769100216810857203198904625400933895331391691459636928060001",
      @"2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397376",
      @"265613988875874769338781322035779626829233452653394495974574961739092490901302182994384699044001"
   };
   return powers[d % 10]; // simple bounds check...
}

And the rest is easy :-)

And if you are wondering, those numbers came from bc - standard command line calculator in U*ix and hence OS X. You could of course invoke bc from Objective-C if you really want to calculate the answers on the fly.

[*] It is not really a "trick" question but asking if you understand that sometimes the best solution is a simple lookup table.

CRD
  • 52,522
  • 5
  • 70
  • 86
0

As you have correctly figured out, you will need to use some sort of big integer library. This is a nice example you can refer to: https://mattmccutchen.net/bigint/

Furthermore, you can calculate x^n in O(lg(n)) rather than in O(n), using divide and conquer:

f(x, n):
    if n == 0:  # Stopping condition
        return 1

    temp = f(n/2)
    result = temp * temp
    if n%2 == 1:
        result *= x

    return result

x = 5  # Or another one digit number.
n = 100
result = f(x, 100)  # This is the result you are looking for.

Note that x represents your integer and n the power you are raising x to.

Neithrik
  • 2,002
  • 2
  • 20
  • 33