Муухай тооны Leetcode шийдэл


Хэцүү байдлын түвшин Easy
Математик

Асуудлын мэдэгдэл

Энэ асуудалд бидэнд дугаар өгдөг бөгөөд энэ нь муухай тоо мөн эсэхийг шалгах ёстой.
Муухай тоонууд нь энгийн хүчин зүйлүүдэд зөвхөн 2, 3, 5 орно.
1-ийг ихэвчлэн муухай тоо гэж үздэг.

Жишээ нь

6
true

Тайлбар: 6 = 2 × 3

14
false

Тайлбар: 14 = 2 × 7
14 нь өөр нэг гол хүчин зүйлийг багтаасан тул муухай биш юм.

арга барил

Асуудлын тодорхойлолтоос харахад муухай тоо байх ёстой бөгөөд энэ нь ямар ч тоог агуулаагүй байх ёстой үндсэн хүчин зүйлүүд 2,3 ба 5-аас бусад.

Тоо бүр нь нэг буюу хэд хэдэн анхны тооны (1-ээс бусад) зарим хүчний үржвэрээр үүсдэг болохыг бид мэднэ. Тиймээс бид тоог анхны хүчин зүйлүүдэд хувааж, 2,3 ба 5-аас бусад анхны тоонуудыг агуулж байгаа эсэхийг харж болно.

Факторчлол гэдэг нь анхны тоо нь тоог бүрэн хувааж чадвал тухайн тооны хүчин зүйл болно гэсэн үг юм. Тиймээс хэрэв тоо 2-т хуваагдвал өгөгдсөн тоог 2-т хувааж, 1-р хүчин зүйлийн 2-р хүчийг хасах болно. Хэрэв бид 2-ын бүх хүчийг тооноос хасах хүртэл 2-оор дахин дахин хуваана.
Үүнтэй адилаар бид 3 ба 5-р хүчин зүйлийн бүх хүчийг арилгах болно.

Одоо энэ тоо 2,3 ба 5-аас бусад анхны хүчин зүйлийг агуулсан бол одоо үлдсэн тоо нь 1-тэй тэнцэхгүй байх нь тодорхой боллоо.
Тиймээс эцэст нь тоо 1 болж хувирвал энэ нь муухай тоо бөгөөд бид буцааж үнэн болно, тэгэхгүй бол бид буцаана.

Хэрэгжүүлэх

Муухай тооны Leetcode шийдэлд зориулсан C ++ програм

#include <bits/stdc++.h>
using namespace std;

bool isUgly(int num) 
{	
  if(num<=0) return false;
   
  while(num%2==0) num/=2;
  while(num%3==0) num/=3;
  while(num%5==0) num/=5;
  
  if(num==1) return true; 
    else return false;
}

int main() 
{
    int num=8;
  
  if(isUgly(num))
    cout<<"true"<<endl;
  else
    cout<<"false"<<endl;

  return 0; 
}
true

Муухай тооны Leetcode шийдлийн Java програм

import java.util.*;
import java.lang.*;


class UglyNumber
{  
   public static boolean isUgly(int num) 
   {
        if(num<=0) return false;
       
        while(num%2==0) num/=2;
        while(num%3==0) num/=3;
        while(num%5==0) num/=5;
        
        if(num==1) return true; 
        else return false;
        
    }
    
    public static void main(String args[])
    {
        int num=8;

        System.out.println(isUgly(num));
        
    }
}
true

Муухай тооны Leetcode шийдлийн нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (бүртгэл (n)): Бид тоог давталтад 2, 3 ба 5-д хувааж байна. Тиймээс цаг хугацааны нарийн төвөгтэй байдал нь O (log (n)) байх бөгөөд n нь тухайн тоо юм.

Сансрын нарийн төвөгтэй байдал 

O (1): Бид нэмэлт зай ашигладаггүй тул тогтмол байдаг.