current position:Home>[algorithm learning] sword finger offer 64 Find 1 + 2 +... + n (Java / C / C + + / Python / go / trust)

[algorithm learning] sword finger offer 64 Find 1 + 2 +... + n (Java / C / C + + / Python / go / trust)

2022-01-29 14:07:01 White hat of the second leader

Thank you very much for reading this article ~ welcome 【 give the thumbs-up 】【 Collection 】【 Comment on 】~ It's not hard to give up , But persistence must be cool ~ I hope all of us can make a little progress every day ~ This paper is written by The white hat of the second leader https://juejin.cn/user/2771185768884824/posts Original blog ~


The finger of the sword Offer 64. seek 1+2+…+n:

seek 1+2+...+n , It is required that multiplication and division shall not be used 、for、while、if、else、switch、case Wait for keywords and conditional statements (A?B:C).

Examples 1

 Input : 
	n = 3
 Output : 
	6
 Copy code 

Examples 2

 Input : 
	n = 9
 Output : 
	45
 Copy code 

Limit

  • 1 <= n <= 10000

analysis

  • The usual practice is to multiply , loop , recursive .
  • The problem does not allow multiplication and circulation , Then use recursion instead of ; Recursion requires a termination condition , The problem is not judged by conditions , We can use short circuit logic operators instead of .
  • Recursion is too slow , We can use the sum formula of the sequence of equal differences , It becomes a calculation n * (n + 1) / 2.
  • Divide 2 You can replace... With a shift to the right .
  • Multiplication , We can consider the steps of multiplication in primary school ,a × b, We just use b Multiply each digit of by a × 10^i^,i Express b The number of digits of , Add up the results . Then if b yes 2 Every bit of the base , It becomes watching b Every one of you is 0 still 1, If it is 1 Just add 1 × a × 2^i^, Replace it with a shift and it becomes a << i.
  • Within limits n The biggest is 10000,2^14^ That's enough .

Answer key

java

class Solution {
    public int sumNums(int n) {
        // 2 Of 14 More than... Times 10000
		//  The summation formula of the sequence of equal differences n * (n + 1) / 2
		int ans = 0, a = n, b = n + 1;
		//  Not much use for eggs. , In order to turn an expression into a statement 
		boolean flag;

		flag = ((b & 1) > 0) && (ans += a) > 0;
		a <<= 1;
		b >>= 1;

		flag = ((b & 1) > 0) && (ans += a) > 0;
		a <<= 1;
		b >>= 1;

		flag = ((b & 1) > 0) && (ans += a) > 0;
		a <<= 1;
		b >>= 1;

		flag = ((b & 1) > 0) && (ans += a) > 0;
		a <<= 1;
		b >>= 1;

		flag = ((b & 1) > 0) && (ans += a) > 0;
		a <<= 1;
		b >>= 1;

		flag = ((b & 1) > 0) && (ans += a) > 0;
		a <<= 1;
		b >>= 1;

		flag = ((b & 1) > 0) && (ans += a) > 0;
		a <<= 1;
		b >>= 1;

		flag = ((b & 1) > 0) && (ans += a) > 0;
		a <<= 1;
		b >>= 1;

		flag = ((b & 1) > 0) && (ans += a) > 0;
		a <<= 1;
		b >>= 1;

		flag = ((b & 1) > 0) && (ans += a) > 0;
		a <<= 1;
		b >>= 1;

		flag = ((b & 1) > 0) && (ans += a) > 0;
		a <<= 1;
		b >>= 1;

		flag = ((b & 1) > 0) && (ans += a) > 0;
		a <<= 1;
		b >>= 1;

		flag = ((b & 1) > 0) && (ans += a) > 0;
		a <<= 1;
		b >>= 1;

		flag = ((b & 1) > 0) && (ans += a) > 0;

		return ans >> 1;
    }
}
 Copy code 

c

int sumNums(int n){
    // 2 Of 14 More than... Times 10000
    //  The summation formula of the sequence of equal differences n * (n + 1) / 2
    int ans = 0, a = n, b = n + 1;

    (b & 1) && (ans += a);
    a <<= 1;
    b >>= 1;

    (b & 1) && (ans += a);
    a <<= 1;
    b >>= 1;

    (b & 1) && (ans += a);
    a <<= 1;
    b >>= 1;

    (b & 1) && (ans += a);
    a <<= 1;
    b >>= 1;

    (b & 1) && (ans += a);
    a <<= 1;
    b >>= 1;

    (b & 1) && (ans += a);
    a <<= 1;
    b >>= 1;

    (b & 1) && (ans += a);
    a <<= 1;
    b >>= 1;

    (b & 1) && (ans += a);
    a <<= 1;
    b >>= 1;

    (b & 1) && (ans += a);
    a <<= 1;
    b >>= 1;

    (b & 1) && (ans += a);
    a <<= 1;
    b >>= 1;

    (b & 1) && (ans += a);
    a <<= 1;
    b >>= 1;

    (b & 1) && (ans += a);
    a <<= 1;
    b >>= 1;

    (b & 1) && (ans += a);
    a <<= 1;
    b >>= 1;

    (b & 1) && (ans += a);

    return ans >> 1;
}
 Copy code 

c++

class Solution {
public:
    int sumNums(int n) {
        // 2 Of 14 More than... Times 10000
        //  The summation formula of the sequence of equal differences n * (n + 1) / 2
        int ans = 0, a = n, b = n + 1;

        (b & 1) && (ans += a);
        a <<= 1;
        b >>= 1;

        (b & 1) && (ans += a);
        a <<= 1;
        b >>= 1;

        (b & 1) && (ans += a);
        a <<= 1;
        b >>= 1;

        (b & 1) && (ans += a);
        a <<= 1;
        b >>= 1;

        (b & 1) && (ans += a);
        a <<= 1;
        b >>= 1;

        (b & 1) && (ans += a);
        a <<= 1;
        b >>= 1;

        (b & 1) && (ans += a);
        a <<= 1;
        b >>= 1;

        (b & 1) && (ans += a);
        a <<= 1;
        b >>= 1;

        (b & 1) && (ans += a);
        a <<= 1;
        b >>= 1;

        (b & 1) && (ans += a);
        a <<= 1;
        b >>= 1;

        (b & 1) && (ans += a);
        a <<= 1;
        b >>= 1;

        (b & 1) && (ans += a);
        a <<= 1;
        b >>= 1;

        (b & 1) && (ans += a);
        a <<= 1;
        b >>= 1;

        (b & 1) && (ans += a);

        return ans >> 1;
    }
};
 Copy code 

python

class Solution:
    def sumNums(self, n: int) -> int:
        # 2 Of 14 More than... Times 10000
        #  The summation formula of the sequence of equal differences n * (n + 1) / 2
        ans = 0
        a = n
        b = n + 1

        (b & 1) and (ans := ans + a)
        a <<= 1
        b >>= 1

        (b & 1) and (ans := ans + a)
        a <<= 1
        b >>= 1

        (b & 1) and (ans := ans + a)
        a <<= 1
        b >>= 1

        (b & 1) and (ans := ans + a)
        a <<= 1
        b >>= 1

        (b & 1) and (ans := ans + a)
        a <<= 1
        b >>= 1

        (b & 1) and (ans := ans + a)
        a <<= 1
        b >>= 1

        (b & 1) and (ans := ans + a)
        a <<= 1
        b >>= 1

        (b & 1) and (ans := ans + a)
        a <<= 1
        b >>= 1

        (b & 1) and (ans := ans + a)
        a <<= 1
        b >>= 1

        (b & 1) and (ans := ans + a)
        a <<= 1
        b >>= 1

        (b & 1) and (ans := ans + a)
        a <<= 1
        b >>= 1

        (b & 1) and (ans := ans + a)
        a <<= 1
        b >>= 1

        (b & 1) and (ans := ans + a)
        a <<= 1
        b >>= 1

        (b & 1) and (ans := ans + a)

        return ans >> 1
 Copy code 

go

func sumNums(n int) int {
    // 2 Of 14 More than... Times 10000
	//  The summation formula of the sequence of equal differences n * (n + 1) / 2
	ans, a, b := 0, n, n + 1
	addGreatZero := func() bool {
		ans += a
		return ans > 0
	}

	_ = ((b & 1) > 0) && addGreatZero()
	a <<= 1
	b >>= 1

	_ = ((b & 1) > 0) && addGreatZero()
	a <<= 1
	b >>= 1

	_ = ((b & 1) > 0) && addGreatZero()
	a <<= 1
	b >>= 1

	_ = ((b & 1) > 0) && addGreatZero()
	a <<= 1
	b >>= 1

	_ = ((b & 1) > 0) && addGreatZero()
	a <<= 1
	b >>= 1

	_ = ((b & 1) > 0) && addGreatZero()
	a <<= 1
	b >>= 1

	_ = ((b & 1) > 0) && addGreatZero()
	a <<= 1
	b >>= 1

	_ = ((b & 1) > 0) && addGreatZero()
	a <<= 1
	b >>= 1

	_ = ((b & 1) > 0) && addGreatZero()
	a <<= 1
	b >>= 1

	_ = ((b & 1) > 0) && addGreatZero()
	a <<= 1
	b >>= 1

	_ = ((b & 1) > 0) && addGreatZero()
	a <<= 1
	b >>= 1

	_ = ((b & 1) > 0) && addGreatZero()
	a <<= 1
	b >>= 1

	_ = ((b & 1) > 0) && addGreatZero()
	a <<= 1
	b >>= 1

	_ = ((b & 1) > 0) && addGreatZero()

	return ans >> 1
}
 Copy code 

rust

impl Solution {
    pub fn sum_nums(n: i32) -> i32 {
        let mut ans = 0;
        let mut a = n;
        let mut b = n + 1;

        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);
        a <<= 1;
        b >>= 1;

        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);
        a <<= 1;
        b >>= 1;

        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);
        a <<= 1;
        b >>= 1;

        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);
        a <<= 1;
        b >>= 1;

        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);
        a <<= 1;
        b >>= 1;

        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);
        a <<= 1;
        b >>= 1;

        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);
        a <<= 1;
        b >>= 1;

        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);
        a <<= 1;
        b >>= 1;

        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);
        a <<= 1;
        b >>= 1;

        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);
        a <<= 1;
        b >>= 1;

        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);
        a <<= 1;
        b >>= 1;

        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);
        a <<= 1;
        b >>= 1;

        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);
        a <<= 1;
        b >>= 1;
        
        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);

        ans >> 1
    }

    fn add_great_zero(ans: &mut i32, n: i32) -> bool {
        *ans += n;
        *ans > 0
    }
}
 Copy code 

 Insert picture description here


Original title transmission gate :https://leetcode-cn.com/problems/qiu-12n-lcof/


copyright notice
author[White hat of the second leader],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201291406571036.html

Random recommended