really Fast C++ solution


  • 0
    I

    Strategy: since only single digits can be valid operands that means that we have 0-9.
    noting that all single digits when prime factored, their factors have to come from the set {2,3,5,7};
    So we do a augmented PrimeFactors functions where we populate only for that set. If anything is left over then we return 0;

    We then can note that we want the minimum number of digits. and we want those digits sorted in ascending order.
    so we can take our factors and split them up into valid sets that represent the 9 valid digits.
    so valid sets are {1}, {3}, {2,2}, {5}, {2,3}, {7}, {2,2,2}, {3,3};
    sorted {1}, {2}, {2,2}, {2,2,2}, {2,3}, {3}, {5}, {7};

    the only question left is if I have both 2's and 3's for factors how do I divy them up?
    Ok so 2,2,3 34 vs 26; should I look at 3's first and
    if only one factor 3 do I combine with a 2
    2,3 6
    2,2, 43 or 26 rule consume a 3,2 (6) before a 2 2's (4)
    2,2,2,3 38 46 rule consume 3 2's(8) before a 3,2 (6)
    i put the minimum set of digits into a string then sort the string in ascending order.
    I then output the string as an int.

    at the time of its submission
    runtime listed a 0ms
    beat 100% of all c++ submissions

    class MinFactors {
    public:
    	unsigned int largestFactor;
    
    	multiset<unsigned int> primeFactors(unsigned int number)
    	{
    		multiset<unsigned int, sComp> factors;
    		while (number % 7==0)
    		{
    			number /= 7;
    			factors.insert(7);
    		}
    		while (number % 5 == 0)
    		{
    			number /= 5;
    			factors.insert(5);
    		}
    		while (number % 3 == 0)
    		{
    			number /= 3;
    			factors.insert(3);
    		}
    		while (number % 2 == 0)
    		{
    			number /= 2;
    			factors.insert(2);
    		}
    		largestFactor = number;
    		return factors;
    
    	}
    	int smallestFactorization(int a) {
    		if (a == 0)
    			return 0;
    		if (a < 10)
    			return a;
    		multiset<unsigned int> factors = primeFactors(a);
    		if (largestFactor > 7)
    			return 0;
    		string answer = "";
    		for (int i = 7; i>3; i--)
    		{
    			if (i == 4 || i == 6)
    			{
    				continue;
    			}
    			auto exist = factors.count(i);
    			if (exist == 0)
    				continue;
    			for (int e = 0; e < exist; e++)
    			{
    				answer += std::to_string(i);
    			}
    		}	
    
    		int twos = factors.count(2);
    		int threes = factors.count(3);
    		while (twos >= 3)
    		{
    			answer += std::to_string(8);
    			twos -= 3;
    		}
    		while (threes >= 2)
    		{
    			answer += std::to_string(9);
    			threes -= 2;
    		}
    		while (threes > 0)
    		{
    			if (twos >= 1)
    			{
    				answer += std::to_string(6);
    				threes--;
    				twos--;
    			}
    			else {
    				answer += std::to_string(3);
    				threes--;
    			}
    		}
    		while (twos >= 1)
    		{
    			if (twos >= 2)
    			{
    				answer += std::to_string(4);
    				twos -= 2;
    			}
    			else if(twos >= 1) {
    				answer += std::to_string(2);
    				twos--;
    			}
    		}
    		std::sort(answer.begin(), answer.end());
    		stringstream ss;
    		ss << answer;
    		unsigned long long bigNum;
    		ss >> std::dec >> bigNum;
    		if (bigNum <= INT_MAX/2)
    		{
    			return (unsigned int) bigNum;
    		}
    		else {
    			return 0;
    		}
    	}
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.