O(1) Archives - Huahua's Tech Road

花花酱 LeetCode 258. Add Digits

By zxi on March 9, 2020

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

Example:

Input: 38
Output: 2 
Explanation: The process is like: 3 + 8 = 11, 1 + 1 = 2. 
             Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

Solution 1: Simulation

Time complexity: O(logn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int addDigits(int num) {

int n = num;

while (n >= 10) {

int t = n;

n = 0;

while (t) {

n += t % 10;

t /= 10;

}

return n;

}

};

Solution 2: Math

https://en.wikipedia.org/wiki/Digital_root#Congruence_formula

Digit root = num % 9 if num % 9 != 0 else min(num, 9) e.g. 0 or 9

Time complexity: O(1)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int addDigits(int num) {

return num % 9 ? num % 9 : min(num, 9);

}

};

花花酱 LeetCode 1323. Maximum 69 Number

By zxi on January 20, 2020

Given a positive integer num consisting only of digits 6 and 9.

Return the maximum number you can get by changing at most one digit (6 becomes 9, and 9 becomes 6).

Example 1:

Input: num = 9669
Output: 9969
Explanation: 
Changing the first digit results in 6669.
Changing the second digit results in 9969.
Changing the third digit results in 9699.
Changing the fourth digit results in 9666. 
The maximum number is 9969.

Example 2:

Input: num = 9996
Output: 9999
Explanation: Changing the last digit 6 to 9 results in the maximum number.

Example 3:

Input: num = 9999
Output: 9999
Explanation: It is better not to apply any change.

Constraints:

1 <= num <= 10^4
num‘s digits are 6 or 9.

Solution: Greedy

Replace the highest 6 to 9, if no 6, return the original number.

Time complexity: O(1)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maximum69Number (int num) {

string s = to_string(num);

for (int i = 0; i < s.length(); ++i) {

if (s[i] == '6') {

s[i] = '9';

return stoi(s);

}

return num;

}

};

花花酱 1276. Number of Burgers with No Waste of Ingredients

By zxi on December 1, 2019

Given two integers tomatoSlices and cheeseSlices. The ingredients of different burgers are as follows:

Jumbo Burger: 4 tomato slices and 1 cheese slice.
Small Burger: 2 Tomato slices and 1 cheese slice.

Return [total_jumbo, total_small] so that the number of remaining tomatoSlices equal to 0 and the number of remaining cheeseSlices equal to 0. If it is not possible to make the remaining tomatoSlices and cheeseSlices equal to 0 return [].

Example 1:

Input: tomatoSlices = 16, cheeseSlices = 7
Output: [1,6]
Explantion: To make one jumbo burger and 6 small burgers we need 4*1 + 2*6 = 16 tomato and 1 + 6 = 7 cheese. There will be no remaining ingredients.

Example 2:

Input: tomatoSlices = 17, cheeseSlices = 4
Output: []
Explantion: There will be no way to use all ingredients to make small and jumbo burgers.

Example 3:

Input: tomatoSlices = 4, cheeseSlices = 17
Output: []
Explantion: Making 1 jumbo burger there will be 16 cheese remaining and making 2 small burgers there will be 15 cheese remaining.

Example 4:

Input: tomatoSlices = 0, cheeseSlices = 0
Output: [0,0]

Example 5:

Input: tomatoSlices = 2, cheeseSlices = 1
Output: [0,1]

Constraints:

0 <= tomatoSlices <= 10^7
0 <= cheeseSlices <= 10^7

Solution: Math

Time complexity: O(1)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> numOfBurgers(int T, int C) {

// Jumbo = x, small = y

// 4x + 2y = T

// x + y = C

// x = (T - 2C) / 2

int x = T / 2 - C;

int y = C - x;

if (4 * x + 2 * y == T && x >= 0 && y >= 0) return {x, y};

return {};

}

};

花花酱 LeetCode 190. Reverse Bits

By zxi on September 30, 2019

Reverse bits of a given 32 bits unsigned integer.

Example 1:

Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

Input: 11111111111111111111111111111101
Output: 10111111111111111111111111111111
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10101111110010110010011101101001.

Note:

Note that in some languages such as Java, there is no unsigned integer type. In this case, both input and output will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 2 above the input represents the signed integer -3 and the output represents the signed integer -1073741825.

Follow up:

If this function is called many times, how would you optimize it?

Solution: Bit operation

Time complexity: O(1)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

uint32_t reverseBits(uint32_t n) {

uint32_t ans = 0;

for (int i = 0; i < 32; ++i) {

ans <<= 1;

ans |= n & 1;

n >>= 1;

}

return ans;

}

};

花花酱 LeetCode 73. Set Matrix Zeroes

By zxi on February 9, 2019

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Example 1:

Input: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
Output: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

Example 2:

Input: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
Output: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

Follow up:

A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

Solution 1

Use two arrays to track whether the i-th row / j-th column need to be zeroed.

Time complexity: O(mn)
Space complexity: O(m+n)

C++

class Solution {

public:

void setZeroes(vector<vector<int>>& matrix) {

const int m = matrix.size();

const int n = matrix[0].size();

vector<int> rows(m);

vector<int> cols(n);

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j) {

rows[i] |= (matrix[i][j] == 0);

cols[j] |= (matrix[i][j] == 0);

}

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j)

if (rows[i] || cols[j]) matrix[i][j] = 0;

}

};

Solution 2

Use the first row / first col to indicate whether the i-th row / j-th column need be zeroed.

C++

class Solution {

public:

void setZeroes(vector<vector<int>>& matrix) {

const int m = matrix.size();

const int n = matrix[0].size();

bool col0 = false;

bool row0 = false;

for (int i = 0; i < m; ++i)

col0 |= (matrix[i][0] == 0);

for (int j = 0; j < n; ++j)

row0 |= (matrix[0][j] == 0);

for (int i = 1; i < m; ++i)

for (int j = 1; j < n; ++j)

if (matrix[i][j] == 0)

matrix[0][j] = matrix[i][0] = 0;

for (int i = 1; i < m; ++i)

for (int j = 1; j < n; ++j)

if (matrix[i][0] == 0 || matrix[0][j] == 0)

matrix[i][j] = 0;

if (row0)

for (int j = 0; j < n; ++j)

matrix[0][j] = 0;

if (col0)

for (int i = 0; i < m; ++i)

matrix[i][0] = 0;

}

};

Posts tagged as “O(1)”

花花酱 LeetCode 258. Add Digits

Solution 1: Simulation

C++

Solution 2: Math

C++

花花酱 LeetCode 1323. Maximum 69 Number

Solution: Greedy

C++

花花酱 1276. Number of Burgers with No Waste of Ingredients

Solution: Math

C++

花花酱 LeetCode 190. Reverse Bits

C++

花花酱 LeetCode 73. Set Matrix Zeroes

Solution 1

C++

Solution 2

C++