Решение за грд број Leetcode


Ниво на тешкотија Лесно
Математика

Изјава за проблем

Во овој проблем ни е даден број и мора да провериме дали е грд број или не.
Со оглед на тоа дека грдите броеви се позитивни броеви чии прости фактори вклучуваат само 2, 3, 5.
Исто така 1 обично се третира како грд број.

пример

6
true

Објаснување: 6 = 2 × 3

14
false

Објаснување: 14 = 2 × 7
14 не е грда бидејќи вклучува друг главен фактор 7.

Пристап

Од изјавата за проблемот, јасно е дека, за да биде грд број, тој не смее да содржи ниеден главни фактори освен 2,3 и 5.

Знаеме дека секој број е формиран од производ на некои моќи од еден или повеќе прости броеви (освен 1). Оттука, можеме да го факторизираме бројот во прости фактори и да видиме дали содржи прости броеви освен 2,3 и 5 или не.

Под факторизација значи ако простиот број може целосно да подели број, тогаш тоа ќе биде фактор на тој одреден број. Затоа, ако бројот е делив со 2, можеме да го поделиме дадениот број со 2, со што ќе ја отстраниме 1-тата моќност на факторот 2. Ние постојано ќе го делиме со 2 додека не се отстранат сите моќности на 2 од бројот.
Слично на тоа, ние ќе ги отстраниме сите моќности на факторите 3 и 5 исто така.

Сега е јасно дека ако бројот содржи други прости фактори освен 2,3 и 5, сегашниот преостанат број не би бил еднаков на 1.
Оттука, конечно, ако бројот стане 1, тогаш тоа е грда бројка и се враќаме вистинито, инаку се враќаме лажни.

Имплементација

Програма 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

Јава програма за решение за грди броеви на леткод

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

Анализа на сложеност за решение за грд број на леткод

Временска комплексност

О (дневник (н)): Ние го делиме бројот со 2, 3 и 5 во додека јамка постојано. Оттука, сложеноста на времето ќе биде O (log (n)), каде што n е дадениот број.

Комплексноста на просторот 

О (1): Ние не користиме дополнителен простор, па затоа е постојан.