Sword finger Offer 64 Find 1 + 2 +... + n

1. Title Description

For 1 + 2 +... + n, it is required that keywords such as multiplication and division, for, while, if, else, switch, case and conditional judgment statements (A?B:C) cannot be used.

Example 1:

Input: n = 3
Output: 6

Example 2:

Input: n = 9
Output: 45

Restrictions:

1 <= n <= 10000

2. Method 1: recursion

1) Ideas and algorithms

Imagine that if you use the recursive method to realize this problem without restriction, I believe everyone can easily give the following implementation (taking C + + as an example):

class Solution{
public:
	int sumNums(int n)
	{
		return n==0 ? 0 : sumNums(n-1);
	}
};

Usually, when implementing recursion, we will use conditional judgment statements to determine the exit of recursion. However, due to the limitation of the problem, we can't use conditional judgment statements. Can we use other methods to determine the exit of recursion? The answer of the logical operator is the nature of the short circuit.

Take the logical operator & & as an example. For the expression A & & B, if the expression A returns False, A & & B has been determined to be False, and expression B will not be executed at this time. Similarly, for the logical operator 𞓜 and the expression A | B, if the expression A returns True, then A | B has been determined to be True, and expression B will not be executed at this time.

Using this feature, we can regard the exit to judge whether it is recursive as part A of A & & B expression, and the recursive main function as part B. If it is not A recursive exit, return True and continue to execute the part of expression B, otherwise the recursion ends. Of course, you can also use the logical operator 𞓜 to give A similar implementation. Here we only provide the recursive implementation combined with the logical operator &.

2) Correct code

class Solution{
public:
	int sumNums(int n)
	{
		n && (n+=sum(n-1));
		return n;
	}
};

Complexity analysis

Time complexity: O(n). The recursive function recurses n times, and the calculation time complexity in each recursion is O(1), so the total time complexity is O(n).
Space complexity: O(n). The spatial complexity of recursive function depends on the depth of recursive call stack. Here, the depth of recursive function call stack is O(n), so the spatial complexity is O(n).

3. Method 2: fast multiplication

When considering the multiplication of A and B, how do we use addition and bit operation to simulate? In fact, it is to expand the binary of B. if the i-th bit under the binary representation of B is 1, then the contribution of this bit to the final result is A * (1 < < I), that is, A < < I. We traverse each bit under the binary expansion of B, and add up all the contributions to get the final answer. This method is also known as Russian farmer multiplication . This method is often used in the scene of multiplying two numbers and taking modulus. If the multiplication of two numbers has exceeded the data range, but will not exceed after taking modulus, we can use this method to disassemble the modulus and calculate the contribution to ensure that each operation is within the data range.

Fast multiplication C + + code

int quickMulti(int A,int B)
{
	int ans=0;
	for(;B;B>>=1)
	{
		if(B&1) ans+=A;
		A<<=1;
	}
	return ans;
}

Back to this question, from the summation formula of the sequence of equal differences, we can know that 1 + 2 + × n is equivalent to n ( n + 1 ) 2 \frac{n(n+1)}{2} 2n(n+1), we can use the shift right operator to simulate the division by 2, then the equation becomes n(n+1) > > 1, and the rest that does not meet the requirements of the topic is n(n+1). According to the fast multiplication mentioned above, we can multiply the two numbers and simulate them with addition and bit operation, but we can see that we still need circular statements in the above C + + implementation, Is there any way to get rid of this circular statement? The answer is yes, that is to manually expand the loop. Because the data range of the topic nn is [110000], the binary expansion of n will not exceed 14 bits at most. We can manually expand 14 layers instead of the loop. So far, the requirements of the topic are met. For specific implementation, please refer to the code given below.

1) Fast multiplicative cyclic expansion method

//Cyclic expansion method of fast multiplication
class Solution{
public:
    int sumNums(int n)
    {
        int ans=0,A=n,B=n+1;
        (A&1)&&(ans+=B);
        A>>=1;
        B<<=1;

        (A&1)&&(ans+=B);
        A>>=1;
        B<<=1;

        (A&1)&&(ans+=B);
        A>>=1;
        B<<=1;

        (A&1)&&(ans+=B);
        A>>=1;
        B<<=1;

        (A&1)&&(ans+=B);
        A>>=1;
        B<<=1;

        (A&1)&&(ans+=B);
        A>>=1;
        B<<=1;

        (A&1)&&(ans+=B);
        A>>=1;
        B<<=1;

        (A&1)&&(ans+=B);
        A>>=1;
        B<<=1;

        (A&1)&&(ans+=B);
        A>>=1;
        B<<=1;

        (A&1)&&(ans+=B);
        A>>=1;
        B<<=1;

        (A&1)&&(ans+=B);
        A>>=1;
        B<<=1;

        (A&1)&&(ans+=B);
        A>>=1;
        B<<=1;

        (A&1)&&(ans+=B);
        A>>=1;
        B<<=1;

        (A&1)&&(ans+=B);
        A>>=1;
        B<<=1;

        return ans>>1;
    }
};

2) Fast multiplication recursion method

(B & 1) in (A & - (B & 1)), only two values can be taken, [0, - 1] and - 1 have a feature when participating in bit and operation, a & - 1 = = a

//Fast multiplication recursion
class Solution{
public:
    int sumNums(int n)
    {
        return quickMulti(n,n+1)>>1;
    }
    int quickMulti(int a,int b)
    {
        int ans=0;  
        (a!=0) && (ans=(b&-(a&1))+quickMulti(a>>1,b<<1));
        return ans;
    }
};

Method 3: using sizeof and array length

C++

class Solution{
public:
	int sumNums(int n)
	{
		bool arr[n][n+1];// The bool variable occupies 1 byte of memory
		return sizeof(arr)>>1;
	}
};