_Gia_Cat_Luong_
Senior Member
Bài toán rẻ rách thật sựGIỜ THÌ TÔI ĐÃ HIỂU TẠI SAO BÀI TOÁN NHẢM NHÍ NÀY LẠI NHIỀU DISLIKE THẾ
Bài toán xàm lông đã chơi giới hạn độ phức tạp thuật toán, giới hạn luôn cả toán tử rồi mà còn giới hạn nốt 32bit int only Mà nó giới hạn unsigned không còn đỡ, đây nó đã chơi signed int thì thuật toán trừ trừ Euclid truyền thống các kiểu dẹp hết. Và để thêm phần ức chế thì phải hơn 1/3 test case là xài giá trị INT_MIN, trong khi giá trị tuyệt đối abs(int min) - abs(int max) = 1, nghĩa là nếu convert từ int min sang số dương thì sẽ gặp lỗi, các hàm abs trên ví dụ cho vui chứ thật ra cũng vứt sọt rác với bài toán nhảm nhí này
Anyway, sau cả 1 buổi chiều rảnh rỗi try hard thì tôi đã dứt điểm được bài toán rẻ rách này với một tý trợ giúp từ wikipedia
View attachment 805274C++:class Solution { public: int bit_size(int arg) { // count the number of bits the argument is using int count = 0; while(arg > 0) { count++; arg = arg >> 1; } return count; } void bit_modify(int& arg, int position, int value) { // change the bit value at #position to value (0 or 1) int bitset = 1 << position; int val = (value != 0) ? 1 : 0; arg = ((arg & ~bitset) | (val << position)); } int bit_value(int arg, int position) // get bit value at #position { return (arg >> position) & 1; } int divide(int dividend, int divisor) { if(dividend == 0) return 0; if(divisor == INT_MIN) { if(dividend == INT_MIN) { return 1; } else { return 0; } } if(dividend == INT_MIN) { if(divisor == INT_MIN) { return 1; } else if(divisor > 0) { int result = divide(dividend + divisor, divisor); return (result > INT_MIN) ? result - 1 : INT_MIN; } else { int result = divide(dividend - divisor, divisor); return (result < INT_MAX) ? result + 1 : INT_MAX; } } if(std::abs(dividend) < std::abs(divisor)) { return 0; } bool negative; if((dividend >= 0 && divisor < 0) || (dividend < 0 && divisor > 0)) { negative = true; } else { negative = false; } int N = std::abs(dividend); // numerator int D = std::abs(divisor); // denominator int R = NULL; //remainder int Q = NULL; //quotient /**************************/ for(int i = bit_size(N) - 1; i >= 0; i--) { R = R << 1; bit_modify(R, 0, bit_value(N, i)); if(R >= D) { R = R - D; bit_modify(Q, i, 1); } } return (negative == false) ? Q : -Q; } };
Edit: nãy đăng lộn bài giải cũ mà sai
Sửa lại rồi nhé