해피 넘버 Leetcode 솔루션

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 Apple
알고리즘 코딩 해싱 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 37

문제 정책

문제는 숫자가 행복한 숫자인지 아닌지 확인하는 것입니다.

숫자가 행복하다고한다 번호 숫자를 자릿수 제곱의 합으로 바꾸고이 과정을 반복하면 숫자가 1이됩니다. 1이되지 않고 1을 포함하지 않는주기에서 끝없이 반복되면 해피 넘버가 아닙니다.

19
true

설명 :

해피 넘버

1 ^ 2 + 9 ^ 2 = 82
8 ^ 2 + 2 ^ 2 = 68
6 ^ 2 + 8 ^ 2 = 100
1 ^ 2 + 0 ^ 2 + 0 ^ 2 = 1 (행복한 숫자)

2
false

설명 :

다시 4 번에 도달하면 여기서부터는 체인에서 영원히 반복되며 1에서 끝날 수 없습니다. 따라서 주어진 숫자는 행복한 숫자가 아닙니다.

접근

우리는 반복 할 수 있습니다 while 루프 그리고 숫자를 1이 될 때까지 숫자의 제곱의 합으로 대체합니다. 이때 새로 변환된 숫자는 이전에 발생하지 않아야 한다는 조건이 적용됩니다. 그렇지 않으면 무한 루프가 됩니다.
이를 위해 처음에는 비어있는 정수 세트를 취하고 다음 단계를 수행 할 수 있습니다.

  1. 현재 숫자가 이미 세트에 있으면 false를 반환합니다 (루프를 찾았습니다).
  2. 그렇지 않으면 1과 같으면 true를 반환합니다.
  3. 그렇지 않으면 현재 숫자를 세트에 삽입하고 현재 숫자를 자릿수 제곱의 합으로 바꿉니다.
  4. 같은 과정을 반복하십시오.

실시

해피 넘버 Leetcode 솔루션을위한 C ++ 프로그램

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

bool isHappy(int n) {
                 
    set<int> s;

    while(s.count(n)==0)
    {
        if(n==1) return true;
        s.insert(n);
        int temp=0;

        while(n)
        {
            temp+= (n%10)*(n%10);
            n/=10;
        }
        n=temp;
    }
    return false;
}

int main()
{ 
    int n=19;
    
    if(isHappy(n)) 
        cout<<"true"<<endl;
    else 
        cout<<"false"<<endl;
    
 return 0;
}
true

해피 넘버 Leetcode 솔루션을위한 자바 프로그램

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

class Happy
{  
     public static boolean isHappy(int n) 
     {
        
        Set<Integer> set = new HashSet<Integer>();
        int sum,digit;

        while (set.add(n)) 
        {
            sum = 0;
            while (n > 0) {
                digit = n%10;
                sum += digit*digit;
                n /= 10;
            }
            if (sum == 1)
                return true;
            else
                n = sum;

        }
        return false;
    }
    
    
    public static void main(String args[])
    {
       int n=19;
       System.out.println(isHappy(n));
    }
}
true

해피 넘버 Leetcode 솔루션의 복잡성 분석

시간 복잡성

O (로그온) :  여기서 n은 주어진 숫자입니다. 연쇄에있는 숫자의 각 자릿수 제곱의 합을 찾는 비용은 log (n)이고 숫자는 대수 인수와 함께 계속 감소합니다. 따라서 복잡성 = O (logn) + O (loglogn) + O (logloglogn) +….
여기서 O (log⁡n)가 지배적 인 부분입니다. 따라서 전체 복잡성은 O (logn)입니다.

공간 복잡성 

O (로그온) :  세트의 최대 크기는 시간 복잡성과 같은 주어진 숫자로 로그됩니다.

코멘트를 남겨

Translate »