Similar Problems
- Fraction To Recurring Decimal
- Prime Palindrome
- Count All Valid Pickup And Delivery Options
- Complex Number Multiplication
- Equal Rational Numbers
- Split Array With Same Average
- Ugly Number Ii
- Divide Array Into Increasing Sequences
- Similar Rgb Color
- Nth Magical Number
- Arithmetic Slices
- Check If It Is A Straight Line
- Projection Area Of 3d Shapes
- Spiral Matrix Iii
- Smallest Good Base
- Sort Transformed Array
- Corporate Flight Bookings
- Poor Pigs
- Largest Triangle Area
- Consecutive Numbers Sum
- Strobogrammatic Number Iii
- Number Of Squareful Arrays
- Powerful Integers
- Sqrtx
- Four Divisors
- Bulb Switcher Ii
- Airplane Seat Assignment Probability
- Numbers At Most N Given Digit Set
- Encode And Decode Tinyurl
- Power Of Two
- Least Operators To Express Number
- 4 Keys Keyboard
- Bulb Switcher
- Power Of Three
- Circular Permutation In Binary Representation
- Binary Gap
- Unknown
- Best Meeting Point
- Minimum Moves To Equal Array Elements Ii
- Confusing Number Ii
- Allocate Mailboxes
- Sum Of Subsequence Widths
- Maximum Product Of Three Numbers
- Rotate Function
- Add Digits
- Number Of Substrings With Only 1s
- Surface Area Of 3d Shapes
- Multiply Strings
- Line Reflection
- Clumsy Factorial
- Check If Array Pairs Are Divisible By K
- The Kth Factor Of N
- Orderly Queue
- Reaching Points
- Broken Calculator
- Excel Sheet Column Title
- Number Of Burgers With No Waste Of Ingredients
- Ugly Number
- Cracking The Safe
- Angle Between Hands Of A Clock
- Valid Boomerang
- Add Binary
- Chalkboard Xor Game
- Day Of The Year
- Squirrel Simulation
- Valid Perfect Square
- Maximum 69 Number
- Valid Tic Tac Toe State
- Add Two Numbers
- Prime Arrangements
- Super Pow
- Palindrome Number
- X Of A Kind In A Deck Of Cards
- Remove 9
- Numbers With Repeated Digits
- Minimum Time To Build Blocks
- Generate Random Point In A Circle
- Armstrong Number
- Valid Number
- Global And Local Inversions
- Robot Bounded In Circle
- Water And Jug Problem
- String To Integer Atoi
- Hexspeak
- Statistics From A Large Sample
- Largest Perimeter Triangle
- Three Equal Parts
- Number Of Digit One
- Encode Number
- Valid Square
- Verbal Arithmetic Puzzle
- Remove Interval
- Self Dividing Numbers
- Find Positive Integer Solution For A Given Equation
- Powx N
- Divide Two Integers
- Convex Polygon
- Rabbits In Forest
- Unknown
- Continuous Subarray Sum
- Self Crossing
- Integer Break
- Maximum Of Absolute Value Expression
- Largest Component Size By Common Factor
- Distribute Candies To People
- Closest Divisors
- Maximum Number Of Ones
- Super Egg Drop
- Optimal Division
- Largest Multiple Of Three
- Minimum Moves To Equal Array Elements
- Reverse Integer
- Set Mismatch
- Fraction Addition And Subtraction
- Check If It Is A Good Array
- Count Substrings With Only One Distinct Letter
- Excel Sheet Column Number
- Perfect Number
- Sum Of Square Numbers
- Path In Zigzag Labelled Binary Tree
- Roman To Integer
- Smallest Integer Divisible By K
- Smallest Range I
- Count Primes
- Stone Game
- Toss Strange Coins
- Max Points On A Line
- Number Of Good Pairs
- Di String Match
- Factorial Trailing Zeroes
- Handshakes That Dont Cross
- Transform To Chessboard
- Integer To Roman
- Subtract The Product And Sum Of Digits Of An Integer
- Find The Derangement Of An Array
- Strobogrammatic Number
- Minimum Area Rectangle Ii
- Integer Replacement
- Complement Of Base 10 Integer
- Range Addition Ii
- Convert Integer To The Sum Of Two No Zero Integers
- Integer To English Words
- Digit Count In Range
- Convert To Base 2
- Super Palindromes
- Missing Number In Arithmetic Progression
- Reordered Power Of 2
- Confusing Number
- Perfect Squares
- Adding Two Negabinary Numbers
- Arranging Coins
- Reach A Number
- Missing Number
- Permutation Sequence
- Escape The Ghosts
- Largest Divisible Subset
- Reverse Subarray To Maximize Array Value
- Reconstruct Original Digits From English
- Happy Number
- Unknown
- Unknown
- Minimize Rounding Error To Meet Target
- Longest Arithmetic Subsequence Of Given Difference
- Rectangle Area
- Nth Digit
- Minimum Factorization
- Rectangle Overlap
- Super Washing Machines
- Basic Calculator
- Count Numbers With Unique Digits
- Simplified Fractions
- Count Triplets That Can Form Two Arrays Of Equal Xor
- Mirror Reflection
- Largest Time For Given Digits
- Smallest Range Ii
- Solve The Equation
- Super Ugly Number
- Divisor Game
Three Divisors - Leetcode Solution
Companies:
LeetCode: Three Divisors Leetcode Solution
Difficulty: Easy
Topics: math
Problem:
Given an integer n, decide if n has a third divisor other than 1 and n.
If you are given an integer n, you are supposed to find out if the integer has 3 divisors, excluding 1 and the integer n itself.
Example 1:
Input: n = 2 Output: false Explanation: There are only two divisors: 1 and 2.
Example 2:
Input: n = 4 Output: true Explanation: The divisors are 1,2,4.
Solution:
The brute-force idea is to start from 2 and check all the numbers in the range of [2,sqrt(n)], whether they are the divisors of n. If there are 3 divisors, return true. Otherwise, return false. The time complexity is O(sqrt(n)).
Here is the code to check whether the integer n has a third divisor other than 1 and n.
class Solution {
public:
bool isThree(int n) {
if (n == 1)
return false;
int cnt = 1;
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0) {
cnt++;
if (i != n / i)
cnt++;
if (cnt > 2)
break;
}
}
return cnt == 2;
}
};
Explanation:
In this code, if n is equal to 1, the function will return false since 1 only has two divisors 1 and itself.
The variable cnt is used to record the number of divisors. We start from 2 and check all the numbers in the range of [2,sqrt(n)], whether they are the divisors of n. If i is a divisor of n and n/i is also a divisor of n, we add 2 into cnt. If i is a divisor of n and n/i is not i, we add 1 into cnt. When cnt is greater than 2, we break the loop.
Finally, we return true if cnt is equal to 2, which means that there are exactly 3 divisors excluding 1 and the integer n itself.
Time Complexity:
The time complexity of this solution is O(sqrt(n)) because we only need to check all the numbers in the range of [2,sqrt(n)].
Three Divisors Solution Code
1class Solution {
2public:
3 int threeDivisors(vector<int>& nums) {
4 int count = 0;
5 for (int i = 0; i < nums.size(); i++) {
6 int divisorCount = 0;
7 int num = nums[i];
8 for (int j = 1; j <= sqrt(num); j++) {
9 if (num % j == 0) {
10 divisorCount++;
11 if (divisorCount > 3) {
12 break;
13 }
14 }
15 }
16 if (divisorCount == 3) {
17 count++;
18 }
19 }
20 return count;
21 }
22};