We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #33: Digit canceling fractions
  4. Discussions

Project Euler #33: Digit canceling fractions

Sort by

recency

|

46 Discussions

|

  • ayanabil297
     + 1 comment

    python code:

    from itertools import combinations, combinations_with_replacement, product

def list_adder(strings, number):
    l = len(strings[0]) + 1
    lis = [string[:i] + str(number) + string[i:] for string in strings for i in range(l)]
    return lis

def permuter(lis1, lis2):
    while lis1:
        n = lis1.pop()
        lis2 = list_adder(lis2, n)
    return set(lis2)

def lis_to_str(list1):
    return ''.join(map(str, list1))

def lis_to_int(list1):
    return int(''.join(map(str, list1)))

def main():
    item = input().split()
    n = int(item[0])
    k = int(item[1])

    li1 = list(combinations_with_replacement(range(1, 10), r=k))
    li2 = list(product(range(10), repeat=n-k))
    li2.remove((0,) * (n - k))

    answers = set()
    li3 = []

    for i in li1:
        li4 = []
        for j in li2:
            li4 += [(lis_to_int(j), int(i)) for i in permuter(list(i), [lis_to_str(j)]) if i[0] != '0']
        li3.append(li4)

    for i in li3:
        for item in combinations(i, r=2):
            if item[0][0] < item[1][0] and item[0][0] * item[1][1] == item[1][0] * item[0][1]:
                answers.add((item[0][1], item[1][1]))

    print(sum(a[0] for a in answers), sum(a[1] for a in answers))

if __name__ == "__main__":
    main()

  • nguyenducdatva
     + 0 comments

    int take_element_4_1 (int a, int b) { int count=0; int res=0; if(b<10) return 0; else if (b>9 && b<100) { res=a-b; if (res%1000 !=0 ) return 0; else return res/1000; } else { while (a) { if (a%10==b%10) { a/=10; b/=10; count ++; } else { res= res*10+a%10;
    a/=10;
    }

         }
    if (count==3) return res; 
    else return 0;
}

    }

    int check_last_case (int a,int b ,int x,int y ) { 

     if (x<10 || y<10 ) return 0; 
else if (x <100 && y<100  ) 
{
        a=take_element_4_1(a,x) ; 
        b=take_element_4_1(b,y) ;
        if (a==0 || b==0) return 0;
        else return (a==b);

}
else {
    a=take_element_4_1(a,x); 
    b=take_element_4_1(b,y);
    if (a==0 || b==0) return 0; 
    else if (a>10 || b>10) return 0; 
    else return (a==b);
}

    }

    main() int i=1; 

    while (i <= 998) {
    int j = i + 1;
    if (j >= 10 * i)
        i++;
    else {
        while (j <= 999) {
            if (GCD(i, j) > 1)
                j++;
            else {
                int cnt = 1000 / i + 1;
                while (j * cnt <= 9999) {
                    for (int u = 1; u <= 999 / j; u++) { 

                        if (check_last_case(i * cnt, j *cnt, i * u, j * u)) {
                            if (d[i * cnt][j * cnt] == 0) {
                                numerator += i * cnt;
                                denominator += j * cnt;

                            }
                            d[i * cnt][j * cnt]++;
                        }
                    }
                    cnt++;
                }
                j++;
            }
        }
        i++;
    }
}

cout<<numerator<<" "<<denominator;

  • ketan_patel25
     + 0 comments

    JAva code

    import java.io.*;
import java.util.*;

public class Solution {

    private static char[] insert(char[] array, int count, char target) {
        char[] in_new = new char[array.length + count];
        for(int k = 0; k < count; k++) {
            in_new[k] = target;
        }
        for(int k = count; k < in_new.length; k++) {
            in_new[k] = array[k - count];
        }
        return in_new;
    }
    
    public static boolean nextPermutation(char[] array) {
        for(int i = array.length - 1; i > 0; i--) {
            if(array[i - 1] < array[i]) {
                int dest = array[i - 1];
                int s = i;
                int e = array.length - 1;
                int swapIndex = 0;
                while(true) {
                    if(s == e) {
                        swapIndex = s;
                        break;
                    }
                    int m = (s + e + 1) / 2;
                    if(array[m] <= dest) {
                        e = m - 1;
                    } else {
                        s = m;
                    }
                }
                char temp = array[swapIndex];
                array[swapIndex] = array[i - 1];
                array[i - 1] = temp;
                Arrays.sort(array, i, array.length);
                return true;
            }
        }
        return false;
    }
    
    private static char[] NumToCharArray(int x, int digits) {
        String result = String.valueOf(x);
        while(result.length() != digits) {
            result = "0" + result;
        }
        return result.toCharArray();
    }
    
    private static int merge(char[] strFill, char[] mask) {
        int index = 0;
        int result = 0;
        for(char m : mask) {
            result *= 10;
            if(m == '.') {
                result += strFill[index] - '0';
                index++;
            } else {
                result += Character.getNumericValue(m);
            }
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        try(Scanner sc = new Scanner(System.in)) {
            int N = sc.nextInt();
            int K = sc.nextInt();
            int keep = N - K;
            int[] Tens = {1, 10, 100, 1000, 10000};
            int sumN = 0;
            int sumD = 0;
            HashSet<Integer> used = new HashSet<>();
            for(int d = 1; d < Tens[keep]; d++) {
                for(int n = 1; n < d; n++) {
                    char[] charN = NumToCharArray(n, keep);
                    char[] charD = NumToCharArray(d, keep);
                    for(int i = Tens[K - 1]; i < Tens[K]; i++) {
                        char[] in = NumToCharArray(i, K);
                        boolean isAscending = true;
                        for(int j = 1; j < in.length; j++) {
                            if(in[j - 1] > in[j]) {
                                isAscending = false;
                                break;
                            }
                        }
                        if(isAscending) {
                            in = insert(in, keep, '.');
                            char[] charInsertN = in.clone();
                            do {
                                int newN = merge(charN,
                                                 charInsertN);
                                if(newN >= Tens[N - 1]) {
                                    char[] charInsertD = in.clone();
                                    do {
                                        int newD = merge(charD,
                                                         charInsertD);
                                        if(newN * d == newD * n) {
                                            int id =   newN
                                                     * 10000
                                                     + newD;
                                            if(!used.contains(id)) {
                                                sumN += newN;
                                                sumD += newD;
                                                used.add(id);
                                            }
                                        }
                                    } while(nextPermutation
                                               (charInsertD));
                                }
                            } while(nextPermutation
                                       (charInsertN));
                        }
                    }
                }
            }
            System.out.println(sumN + " " + sumD);
        }
    }
}

  • vidush_rk11
     + 0 comments

    Some points as also mentioned by other programmers
    1) You can't cancel any 0, irrespective of whatever position it is at.
    2) 0's at end are allowed as long as point 1 is followed.
    3) You have to 'cancel' common digits in numerator and denominator not reduce the fractions, and hence the order of digits can be any.
    4) Don't repeat count fractions

    100points/- python 3

    import itertools
def list_adder(strings,number):
    '''Create all possible strings with number added at all indices in string in strings'''
    l=len(strings[0])+1 #+1, because I also have to add number at last position 
    lis=[string[:i]+str(number)+string[i:] for string in strings for i in range(l)]
    return lis

def permuter(lis1,lis2):
    '''It creates all possible permutations with lis1 as unordered and lis2 as ordered'''
    while lis1:
        n=lis1.pop()
        lis2=list_adder(lis2,n)
    return set(lis2)

def lis_to_str(list1):
    '''Take in a sequence of numbers and returns a str of them'''
    return ''.join([str(no) for no in list1])

def lis_to_int(list1):
    '''Take in a sequence of numbers and return int formed by combining them'''
    return int(''.join([str(no) for no in list1]))

item=input().split()
n=int(item[0])
k=int(item[1])

li1=list(itertools.combinations_with_replacement(range(1,10),r=k)) #This is the list of possible combinations of numbers which are common in numerator and denominator

li2=list(itertools.product(range(10),repeat=n-k)) #The ordered combinations of other digits in numerator or denominator
li2.remove((0,)*(n-k)) # after cancelling common digits we should'nt be left with something like 00/00 or 00/12 etc

answers=set() #so that I don't count repeated fractions
li3=[] # it contains for a particular element in li all the possible casses of elements in li2 with the numerator or denominator as in the format (12,1234) all stored in a list
for i in li1:
    li4=[]
    for j in li2:
        li4+=[(lis_to_int(j),int(i)) for i in permuter(list(i),[lis_to_str(j)]) if i[0]!='0'] # we should'nt get number like 0123 for n=4
    li3.append(li4)

for i in li3:
    for item in itertools.combinations(i,r=2): # I just used combinations instead of permutations cause the left over numerator should be less than left over denominator and the storing order was lexicographical
        if item[0][0]<item[1][0] and item[0][0]*item[1][1]==item[1][0]*item[0][1]:
            answers.add((item[0][1],item[1][1]))

print(sum([a[0] for a in answers]), sum([a[1] for a in answers]))

    `

  • adyanta_b_sriva1
     + 0 comments

    here is my submission in java, i have tested the code and provides correct results in almost all tests using the help from the discussions below however i failed the timeout, if anyone wants some refrence you can refer below-

    import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set;

    public class Main { public static void main(String[] args) { int n = 4; int k = 3;

        Set<String> fractions = new HashSet<>();

    for (int numerator = (int) Math.pow(10, n - 1); numerator < Math.pow(10, n); numerator++) {
        for (int denominator = numerator + 1; denominator < Math.pow(10, n); denominator++) {
            String numeratorString = Integer.toString(numerator);
            String denominatorString = Integer.toString(denominator);

            for (int i = 0; i < numeratorString.length(); i++) {
                char numeratorChar = numeratorString.charAt(i);
                for (int j = 0; j < denominatorString.length(); j++) {
                    char denominatorChar = denominatorString.charAt(j);

                    if (numeratorChar == '0' || denominatorChar == '0') {
                        continue;
                    }

                    if (numeratorChar == denominatorChar) {
                        String numeratorReduced = numeratorString.substring(0, i) + numeratorString.substring(i + 1);
                        String denominatorReduced = denominatorString.substring(0, j) + denominatorString.substring(j + 1);

                        if (denominatorReduced.equals("0")) {
                            continue;
                        }

                        double originalFraction = (double) numerator / denominator;
                        double reducedFraction = (double) Integer.parseInt(numeratorReduced) / Integer.parseInt(denominatorReduced);

                        if (originalFraction == reducedFraction) {
                            fractions.add(numerator + "," + denominator);
                        }
                    }
                }
            }
        }
    }

    int numeratorSum = 0;
    int denominatorSum = 0;

    List<String> fractionList = new ArrayList<>(fractions);
    for (int i = 0; i < fractionList.size(); i++) {
        String[] fraction = fractionList.get(i).split(",");
        int numerator = Integer.parseInt(fraction[0]);
        int denominator = Integer.parseInt(fraction[1]);

        numeratorSum += numerator;
        denominatorSum += denominator;
    }

    System.out.println(numeratorSum + " " + denominatorSum);
}

    }