NC638 简单的变换

给你一个正整数n，重复进行以下操作：
1.如果n是奇数，令n=n−3
2.如果n是偶数，令n=n/2
重复上述直至n=0停止，请输出进行操作的次数，如果n永远无法变成零，输出-1

案例
输入：9
返回值：3
说明：
1.9->6(9-3=6)
2.6->3(6/2=3)
3.3->0(3-3=0)
三步操作后n变为0，所以返回3。

方法一 数学

如果n是3的倍数则说明不可能减到0否则暴力计算,题目中规定每次可以选n-3 和 n/2，很明显一个数n到0的最后一步一定是-3，以此往前推,假设n不是为的倍数那么最后一步一定小于3且大于0，例如8不是3的倍数一直减3最后的结果将会是2无法将值变为0,对于/2的情况只是将原先3的倍数缩小。

class Solution {
public:
    int Numberofoperations(long long n) {
        // write code here
        int ans = 0;
        if(n % 3) return -1; //如果不是3的倍数就不是不可能计算成0
        while(n){
            if(n % 2) n -= 3; //奇数操作
            else n /= 2;//偶数操作
            ans ++;//更新答案
        }
        return ans;
    }
};

时间复杂度： $O\left(logn\right)O(logn)$O(logn) 交替对n除2的最多次数
空间复杂度： $O\left(1\right)O(1)$O(1) 使用若干个变量

方法二 暴力

直接暴力跑如果n小于2且不等于0则说明无法等于0

class Solution {
public:
    int Numberofoperations(long long n) {
        // write code here
        int ans = 0;
        while(n){
            if(n == 1) return -1; //如果=3说明不可能继续操作了
            if(n % 2) n -= 3; //奇数操作
            else n /= 2;//偶数操作
            ans ++;//更新答案
        }
        return ans;
    }
};

时间复杂度： $O\left(logn\right)O(logn)$O(logn) 交替对n除2的最多次数
空间复杂度： $O\left(1\right)O(1)$O(1) 使用若干个变量