Как проверить, является ли число цветным номером?

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; 

}