Interview Practice 12 – Sum from 1 to N Unconventionally

Question

Sum up 1 to n without using division, multiplication, for loop, while loop, if else, switch and condition statement (A?B:C).

Solution 1

Actually, for loop can be simulated through making use of the static property. Since static value will be stored in the class, we can increase the value every time we init a static class.

#include <iostream.h>

class Temp
{
public:
    Temp() {
        ++N;
        Sum += N;
    }
    static void Reset() { N = 0; Sum = 0; }
    static int GetSum() { return Sum; }

private:
    static int N;
    static int Sum;
};

int Temp::N = 0;
int Temp::Sum = 0;

int solution1_Sum(int n)
{
    Temp::Reset();
    Temp *a = new Temp[n];   //就是这个意思,new出n个数组。
    delete []a;
    a = 0;
    return Temp::GetSum();
}

int main()
{
    cout<<solution1_Sum(100)<<endl;
    return 0;
}

//运行结果:
//5050
//Press any key to continue

Solution 2

既然不能判断是不是应该终止递归,我们不妨定义两个函数。
一个函数充当递归函数的角色,另一个函数处理终止递归的情况,
我们需要做的就是在两个函数里二选一。

从二选一我们很自然的想到布尔变量,
比如ture/(1)的时候调用第一个函数,false/(0)的时候调用第二个函数。
那现在的问题是如和把数值变量n转换成布尔值。

如果对n连续做两次反运算,即!!n,那么非零的n转换为true,0转换为false。

#include <iostream.h>

class A;
A* Array[2];

class A
{
public:
    virtual int Sum (int n) { return 0; }
};

class B: public A
{
public:
    virtual int Sum (int n) { return Array[!!n]->Sum(n-1)+n; }
};

int solution2_Sum(int n)
{
    A a;
    B b;
    Array[0] = &a;
    Array[1] = &b;
    int value = Array[1]->Sum(n);
    //利用虚函数的特性,当Array[1]为0时,即Array[0] = &a; 执行A::Sum,
    //当Array[1]不为0时,即Array[1] = &b; 执行B::Sum。
    return value;
}

int main()
{
    cout<<solution2_Sum(100)<<endl;
    return 0;
}

//5050
//Press any key to continue

 

Leave a Reply

%d bloggers like this: