Çirkin Sayı Leetcode Həlli

Çətinlik səviyyəsi Asan
alqoritmlər kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions RiyaziyyatBaxılıb 32

Problem bəyanat

Bu problemdə bizə bir nömrə verilir və bunun çirkin bir rəqəm olub olmadığını yoxlamalıyıq.
Çirkin rəqəmlərin əsas amillərinə yalnız 2, 3, 5 daxil olan müsbət rəqəmlər olduğunu nəzərə alsaq.
Həm də 1 adətən çirkin bir rəqəm kimi qəbul edilir.

misal

6
true

İzahat: 6 = 2 × 3

14
false

İzahat: 14 = 2 × 7
14, başqa bir başlıca amil 7-ni əhatə etdiyi üçün çirkin deyil.

Yanaşma

Problem problemindən aydın olur ki, çirkin bir rəqəm olmaq üçün heç birinin olmaması lazımdır əsas amillər 2,3 və 5-dən başqa.

Hər bir ədədin bir və ya bir neçə əsas ədədin bəzi güclərinin məhsulu ilə əmələ gəldiyini bilirik (1 istisna olmaqla). Beləliklə, ədədi əsas amillərinə bölərək 2,3 və 5-dən başqa sadə ədədlərin olub-olmadığını görə bilərik.

Faktorlaşdırma dedikdə, sadə bir ədədi bir ədədi tamamilə bölə bilərsə, o zaman bu həmin ədədin amili olacaqdır. Buna görə də rəqəm 2-yə bölünürsə, verilmiş ədədi 2-yə bölə bilərik, beləliklə amil 1-nin 2-ci gücünü çıxarırıq. 2-nin bütün gücləri saydan çıxana qədər dəfələrlə 2-yə böləcəyik.
Eyni şəkildə faktor 3 və 5-in bütün güclərini də aradan qaldıracağıq.

İndi aydındır ki, sayda 2,3 və 5-dən başqa hər hansı bir əsas amil varsa, cari qalan rəqəm 1-ə bərabər olmazdı.
Nəhayət, rəqəm 1 olarsa, çirkin bir rəqəmdir və doğru qayıdırıq, əksinə yalan qaytarırıq.

Həyata keçirilməsi

Çirkin Sayı Leetcode Həlli üçün C ++ Proqramı

#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

Çirkin Sayı Leetcode Həlli üçün Java Proqramı

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

Çirkin Sayı Leetcode Həlli üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (log (n)): Nömrəni 2, 3 və 5 -ə bölürük döngə zamanı dəfələrlə. Beləliklə, vaxtın mürəkkəbliyi O (log (n)) olacaq, burada n verilən rəqəmdir.

Kosmik Mürəkkəblik 

O (1): Əlavə yer istifadə etmirik, buna görə də sabitdir.

Şərh yaz

Translate »