psbook solutions

সমস্যা ও সমাধান বই - ১ এর উপর অনুশীলন ( Practice code for Problem and Solutions Book - 1 by Mahbubul Hasan )

View the Project on GitHub

Timus 1014 - Product of Digits

Greedy

গ্রীডি টেকনিকে খুবই সহজে সমাধান করা সম্ভব। ৯ থেকে ২ পর্যন্ত সংখ্যাগুলো দিয়ে যতবার ভাগ যায় ভাগ দিতে থাকব আর সংখ্যাগুলো লিখে রাখব। যদি শেষে ১ থাকে তাহলে সমাধান আছে।লিখে রাখা সংখ্যাগুলো উল্টা অর্ডারে প্রিন্ট করব।

Time O(n)
Commit Time 15 Oct 2017 14:44
#include <bits/stdc++.h>

using namespace std;

int n;

int main() {
    scanf("%d", &n);
    vector<int> ans;
    if(n == 1) {
        printf("1\n");
        return 0;
    } else if(n == 0) {
        printf("10\n");
        return 0;
    }
    for(int i = 9;i >= 2;--i) {
        while(n % i == 0) {
            n /= i;
            ans.push_back(i);
        }
    }
    if(n == 1) {
        for (int i = ans.size()-1; i >= 0; --i) {
            printf("%d", ans[i]);
        }
        printf("\n");
    } else {
        printf("-1\n");
    }
    return 0;
}