Ҳалли рақами зишткунандаи 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 ++ барои ҳалли рақамҳои зишти Leetcode

#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

Барномаи Java барои ҳалли рақамҳои зишти Leetcode

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 (log (n)): Мо рақамро бо такрор ба такрор такроран ба 2, 3 ва 5 тақсим мекунем. Аз ин рӯ, мураккабии вақт O (log (n)) хоҳад буд, ки дар он n шумораи додашуда мебошад.

Мураккабии фазо 

О (1): Мо ягон фазои иловагиро истифода намебарем, аз ин рӯ он доимист.