숫자가 컬러 넘버인지 어떻게 확인할 수 있습니까?

Question

다채로운 번호 :

숫자는 다른 하위 시퀀스 부분으로 나눌 수 있습니다. 예를 들어, 숫자 3245는 3 2 4 5 32 24 45 324 245과 같은 부분으로 나눌 수 있습니다. 그리고이 숫자는 다채로운 숫자입니다. 서브 시퀀스의 모든 숫자의 곱이 다르기 때문입니다. 즉, 3 2 4 5 (3*2)=6 (2*4)=8 (4*5)=20 (3*2*4)= 24 (2*4*5)= 40

그러나 326은 3 2 6 (3*2)=6 (2*6)=12을 생성 할 때 화려한 숫자가 아닙니다.

주어진 숫자가 다채로운 숫자인지 아닌지 알려주는 함수를 작성해야합니다.

Answer 1

직접적인 해결책은 모든 제품을 열거하고이를 해시 맵에 기록하는 것입니다.

당신은 이중 루프에서 모든 제품을 열거 :

• 를 시작 인덱스를 증가;

• 끝 인덱스를 증가시켜 매번 현재 숫자를 곱합니다.

  3, 3.2, 3.2.4, 3.2.4.5; 2, 2.4, 2.4.5; 4, 4.5; 5

당신은이 모든 제품을 생성하는 확인할 수 있습니다

. (또한 전체 시퀀스의 제품을 생성하지만 추가 솔루션을 생성하지 않으므로 무해합니다.) 최악의 경우, 즉 색이 화려한 경우 숫자 O (N²) 시간이 소요됩니다. 해시 맵 삽입과 검색은 상수 시간 연산이라고 가정합니다.

Answer 2

이미이 문제에 대한 O (n²) 해결책이 있습니다. 누구에게나 더 나은 해결책이 있습니다.

package ProblemSolving; 

import java.io.BufferedReader; 
import java.io.InputStreamReader; 
import java.lang.Exception; 
import java.lang.Integer; 
import java.lang.String; 
import java.lang.System; 
import java.util.HashSet; 
import java.util.Set; 

/** 
* Colorful Number: 
* A number can be broken into different sub-sequence parts. 
* Suppose, a number 3245 can be broken into parts like 3 2 4 5 32 24 45 324 245. 
* And this number is a colorful number, since product of every digit of a 
* sub-sequence are different. 
* That is, 3 2 4 5 (3*2)=6 (2*4)=8 (4*5)=20 (3*2*4)= 24 (2*4*5)= 40 
* But 326 is not a colorful number as it generates 3 2 6 (3*2)=6 (2*6)=12. 
*/ 
public class ColorfulNumber { 
public static void main(String[] args) throws Exception { 
    String numString = new BufferedReader(new InputStreamReader(System.in)).readLine(); 
    int num = Integer.parseInt(numString); 
    int length = numString.length(); 
    int[] digits = new int[length]; 
    int index = length - 1; 
    Set<Integer> productSet = new HashSet<Integer>(); 

    while (num > 0) { 
     digits[index] = num % 10; 
     if(productSet.contains(digits[index])) 
     { 
      System.out.println("Not a colorful number"); 
      return; 
     }else{ 
      //System.out.println("Added "+digits[index]+" at "+index); 
      productSet.add(digits[index]); 
     } 
     num = num/10; 
     index--; 
    } 
    for (int x = 1; x < length; x++) { 
     int product = 1; 
     for(int i=0;i<x;i++) 
     { 
      product = product*digits[i]; 
     } 

     for (int y = x; y < length; y++) { 
      if(productSet.contains(product * digits[y])) 
      { 
       System.out.println("Not a colorful number"); 
       //System.out.println("Not a colorful number "+ product * digits[y]+" exists"); 
       return; 
      }else{ 
       //System.out.println("Added "+ product * digits[y]); 
       productSet.add(product * digits[y]); 
      } 
     } 
    } 
    System.out.println("Colorful number"); 
} 

}

Answer 3

이를 확인하시기 바랍니다. 테스트 케이스를 놓친 경우 나에게 알려주십시오.

public int colorful(int a) { 

    String s = String.valueOf(a); 

    Set<Integer> set = new HashSet<>(); 

    int temp = 0; 

    while (temp < s.length()) { 
     //If consecutive Integer is same return 0 
     if (set.contains(s.charAt(temp) - '0')) return 0; 
     set.add(s.charAt(temp) - '0'); 
     temp++; 
    } 

    int i = 0; 
    int j = 1; 
    int n = s.length(); 

    int val1 = 0; 
    int val2 = 0; 

    while (j < n) { 

     val1 = s.charAt(i) - '0'; 
     val2 = s.charAt(j) - '0'; 

     if (set.contains(val1*val2)) 
      return 0; 

     set.add(val1 * val2); 

     i++; 
     j++; 
    } 
    return 1; 
} 

Answer 4

다음 코드는

public int colorful(int A) { 
    HashSet<Integer> hashSet = new HashSet<>(); 
    ArrayList<Integer> numbers = new ArrayList<>(); 

    while (A != 0) { 
     int num = A % 10; 
     numbers.add(num); 
     A /= 10; 
    } 

    Collections.reverse(numbers); 
    int n = numbers.size(); 

    for (int i = 0; i < n; i++) { 
     for (int j = i; j < n; j++) { 
      int prod = 1; 
      for (int k = i; k <= j; k++) { 
       prod = prod * numbers.get(k); 
      } 
      if (hashSet.contains(prod)) 
       return 0; 
      hashSet.add(prod); 
     } 
    } 

    return 1; 

}