Powerful Integers

Given two positive integers x and y, an integer is powerful if it is equal to x^i + y^j for some integers i >= 0 and j >= 0. Return a list of all powerful integers that have value less than or equal to bound. You may return the answer in any order. In your answer, each value should occur at most once. Example 1 Input: x = 2, y = 3, bound = 10 Output: [2,3,4,5,7,9,10] Explanation: 2 = 2^0 + 3^0 3 = 2^1 + 3^0 4 = 2^0 + 3^1 5 = 2^1 + 3^1 7 = 2^2 + 3^1 9 = 2^3 + 3^0 10 = 2^0 + 3^2 Example 2 Input: x = 3, y = 5, bound = 15 Output: [2,4,6,8,10,14] Note 1 <= x <= 100 1 <= y <= 100 0 <= bound <= 10^6 Hint If x^i > bound, the sum x^i + y^j can’t be less than or equal to the bound.

by lek tin in "algorithm" access_time 2-min read

Consecutive Numbers Sum

Given a positive integer N, how many ways can we write it as a sum of consecutive positive integers? Example 1 Input: 5 Output: 2 Explanation: 5 = 5 = 2 + 3 Example 2 Input: 9 Output: 3 Explanation: 9 = 9 = 4 + 5 = 2 + 3 + 4 Example 3 Input: 15 Output: 4 Explanation: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5 Note 1 <= N <= 10 ^ 9.

by lek tin in "algorithm" access_time 1-min read

Strobogrammatic Number

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Write a function to determine if a number is strobogrammatic. The number is represented as a string. Example 1 Input: "69" Output: true Example 2 Input: "88" Output: true Example 3 Input: "962" Output: false Solution class Solution: def isStrobogrammatic(self, num: str) -> bool: pairs = { 1: 1, 6: 9, 8: 8, 9: 6, 0: 0 } mid = len(num)//2+1 for i in range(mid): leftNum = int(num[i]) rightNum = int(num[-i-1]) if leftNum not in pairs or pairs[leftNum] !

by lek tin in "algorithm" access_time 1-min read

Sum of Square Numbers

Given a non-negative integer c, your task is to decide whether there’re two integers a and b such that a2 + b2 = c. Example 1 Input: 5 Output: True Explanation: 1 * 1 + 2 * 2 = 5 Example 2 Input: 3 Output: False Solution import math class Solution: def judgeSquareSum(self, c: int) -> bool: if c <= 1: return True sqrt = math.ceil(math.sqrt(c)) left, right = 0, sqrt-1 while left*left + right*right < c: if (left+1)*(left+1) + right*right > c: right -= 1 else: left += 1 if left*left + right*right == c: return True return False Without sqrt function

by lek tin in "algorithm" access_time 1-min read

Valid Perfect Square

Given a positive integer num, write a function which returns True if num is a perfect square else False. Note Do not use any built-in library function such as sqrt. Example 1 Input: 16 Output: true Example 2 Input: 14 Output: false Solution (naive) Java class Solution { public boolean isPerfectSquare(int num) { if (num == 1) return true; for (int i = 2; i < num; i++) { if (i * i == num) { return true; } if (i * i > num) { break; } } return false; } } Solution (Binary Search version 1) Let x be the square root, 1 < x < num/2 always holds true.

by lek tin in "algorithm" access_time 2-min read

Valid Number

Validate if a given string can be interpreted as a decimal number. Some examples: "0" => true " 0.1 " => true "abc" => false "1 a" => false "2e10" => true " -90e3 " => true " 1e" => false "e3" => false " 6e-1" => true " 99e2.5 " => false "53.5e93" => true " --6 " => false "-+3" => false "95a54e53" => false Note It is intended for the problem statement to be ambiguous.

by lek tin in "algorithm" access_time 3-min read

Happy Number

Write an algorithm to determine if a number is “happy”. A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

by lek tin in "algorithm" access_time 1-min read