[Easy] Algo challenge #2

Raul · December 13, 2018

De data aceasta, propun un challenge care nu necesita prea multe cunostinte in structuri de date, ci o logica buna.

O definitie necesara: In matematica, un numar Kaprekar, pentru o baza data, este un numar intreg si pozitiv, al carui valoare ridicata la patrat, in aceeasi baza, poate fi impartita in doua bucati, iar suma numerelor din aceste doua bucati rezulta efectiv in numarul original. Numarul se imparte in doua parti egale (sau +1 la una dintre parti, atunci cand este un numar impar de cifre), nu se fac "variante". Exemplu: 45 este un numar care respecta regula (numar Kaprekar), deoarece 45² = 2025 si 20+25 = 45.

Alte exemple: 9 respecta regula, deoarece 9² = 81 si 8+1 = 9; 297 respecta regula, deoarece 297² = 88209 si 88 + 209 = 297.

ATENTIE: Aceasta nu reprezinta definitia oficiala in totalitate, este o variatie, problema trebuie rezolvata pe baza la ce se spune aici.

A se observa ca in ultimul exemplu, numarul ridicat la patrat se imparte intr-o bucata de lungime doi si celalalta de lungime trei, deoarece are un numar impar de cifre, fata de cazurile in care ar fi un numar par de cifre. De asemenea, trebuie avut grija, daca una dintre cele doua bucati incepe cu un 0.

Se dau doua numere intregi, p si q, si se cere sa se afiseze toate numerele Kaprekar din respectivul interval (inclusiv p si q); 0 < p < q < 100000

Exemplu: p = 1, q = 100; se va afisa "1 9 45 55 99", acestea fiind numerele care respecta regula.

Limbajul care va fi folosit este la alegere libera. Solutiile cu complexitate timp mai mare decat O(N) sunt respinse. O solutie personala va fi pusa ulterior.

Spor!

Edited December 15, 2018 by Raul

theandruala · December 14, 2018

public class MuieGO {

	public static void main(String[] args) {
		
		int p=1;
		int q=10000000;
		long startTime = System.currentTimeMillis();
		for (int i = p; i <= q; i++) {
			if(check(i))System.out.print(i+"  ");
		}
		System.out.println();
		System.out.println(System.currentTimeMillis()-startTime + " milliseconds");
	}

	static boolean check(long nr) {
		long numar = nr * nr;
		int lungime = String.valueOf(numar).length();
		long jum1 = 0, jum2 = 0;
		if (lungime % 2 == 0) {
			jum1 = (long) (numar / Math.pow(10, (lungime / 2)));
			jum2 = (long) (numar % Math.pow(10, (lungime / 2)));
		} else {
			jum1 = (long) (numar / Math.pow(10, (lungime / 2) + 1));
			jum2 = (long) (numar % Math.pow(10, (lungime / 2) + 1));
		}

		return (jum1 + jum2 == nr);
	}
}

1 9 45 55 99 297 703 999 2223 2728 4950 5050 7272 7777 9999 17344 22222 77778 82656 95121 99999 142857 148149 181819 187110 208495 318682 329967 351352 356643 390313 461539 466830 499500 500500 533170 538461 609687 643357 648648 670033 681318 791505 812890 818181 851851 857143 961038 994708 999999 4444444 4927941 5072059 5555556 9372385 9999999
2319 milliseconds

Edited December 14, 2018 by theandruala

Raul · December 14, 2018

39 minutes ago, theandruala said:
public class MuieGO {

	public static void main(String[] args) {
		
		int p=1;
		int q=10000000;
		long startTime = System.currentTimeMillis();
		for (int i = p; i <= q; i++) {
			if(check(i))System.out.print(i+"  ");
		}
		System.out.println();
		System.out.println(System.currentTimeMillis()-startTime + " milliseconds");
	}

	static boolean check(long nr) {
		long numar = nr * nr;
		int lungime = String.valueOf(numar).length();
		long jum1 = 0, jum2 = 0;
		if (lungime % 2 == 0) {
			jum1 = (long) (numar / Math.pow(10, (lungime / 2)));
			jum2 = (long) (numar % Math.pow(10, (lungime / 2)));
		} else {
			jum1 = (long) (numar / Math.pow(10, (lungime / 2) + 1));
			jum2 = (long) (numar % Math.pow(10, (lungime / 2) + 1));
		}

		return (jum1 + jum2 == nr);
	}
}
1 9 45 55 99 297 703 999 2223 2728 4950 5050 7272 7777 9999 17344 22222 77778 82656 95121 99999 142857 148149 181819 187110 208495 318682 329967 351352 356643 390313 461539 466830 499500 500500 533170 538461 609687 643357 648648 670033 681318 791505 812890 818181 851851 857143 961038 994708 999999 4444444 4927941 5072059 5555556 9372385 9999999
2319 milliseconds

Am testat, solutia este valida, kudos!

Sunt binevenite si alte propuneri, in continuare.

Edited December 14, 2018 by Raul

TheOne01 · December 14, 2018

Salut, mi se pare mie sau algoritmul prezentat de theandruala nu merge chiar asa bine ?

Mai sunt numere care sunt Kaprekar, dar nu sunt afisate: de exemplu 4879

#include <iostream>

using namespace std;

bool isKaprekar(uint64_t k)
{
    uint64_t q, r, n = 10, kp = k*k;

    if(k == 1) return true;

    while(kp > n)
    {
        q = kp/n;
        r = kp%n;
        if(q + r == k && q > 0 && r > 0) return true;
        n *= 10;
    }
    return false;
}

int main()
{
    uint64_t p, q, i;
    cin>>p>>q;

    for(i=p; i<=q; i++)
        if(isKaprekar(i)) cout<<i<<" ";

    return 0;
}

theandruala · December 14, 2018

1 hour ago, TheOne01 said:

Salut, mi se pare mie sau algoritmul prezentat de theandruala nu merge chiar asa bine ?

Mai sunt numere care sunt Kaprekar, dar nu sunt afisate: de exemplu 4879


#include <iostream>

using namespace std;

bool isKaprekar(uint64_t k)
{
    uint64_t q, r, n = 10, kp = k*k;

    if(k == 1) return true;

    while(kp > n)
    {
        q = kp/n;
        r = kp%n;
        if(q + r == k && q > 0 && r > 0) return true;
        n *= 10;
    }
    return false;
}

int main()
{
    uint64_t p, q, i;
    cin>>p>>q;

    for(i=p; i<=q; i++)
        if(isKaprekar(i)) cout<<i<<" ";

    return 0;
}

4879 ^ = 23804641

2380 + 4641 NU DA 4879

Raul · December 14, 2018

18 hours ago, TheOne01 said:

Salut, mi se pare mie sau algoritmul prezentat de theandruala nu merge chiar asa bine ?

Mai sunt numere care sunt Kaprekar, dar nu sunt afisate: de exemplu 4879


#include <iostream>

using namespace std;

bool isKaprekar(uint64_t k)
{
    uint64_t q, r, n = 10, kp = k*k;

    if(k == 1) return true;

    while(kp > n)
    {
        q = kp/n;
        r = kp%n;
        if(q + r == k && q > 0 && r > 0) return true;
        n *= 10;
    }
    return false;
}

int main()
{
    uint64_t p, q, i;
    cin>>p>>q;

    for(i=p; i<=q; i++)
        if(isKaprekar(i)) cout<<i<<" ";

    return 0;
}

Exemplul dat cu 4879 este gresit, nefiind un numar Kaprekar (pe baza definitiei din textul problemei), dupa cum a demonstrat si Andruk. Bazeaza-te pe definita data in textul problemei, nu pe altceva. Am modificat acum ca sa fie mai clar, acum sigur nu mai sunt dileme. Imi pare rau pentru confuzia creata!

Rezolvarea ta nu este corecta, ai 3/7 testcase-uri care pica. In principal, problema e ca nu validezi corect si apar numere care nu sunt Kaprekar (evident, pe baza definitiei din textul problemei). Exemplu:

Input: p = 1000, q = 10000
Output asteptat: 2223 2728 4950 5050 7272 7777 9999
Output-ul tau: 2223 2728 4879 4950 5050 5292 7272 7777 9999

LE: Solutia mea (Golang) este urmatoarea:

func kaprekar(p, q int64) {
    for i := p; i <= q; i++ {
        x := i * i
        xS := len(fmt.Sprintf("%d", x))
        if xS % 2 == 1 {
            xS++
        }
        d := int64(math.Pow(10, float64(xS/2)))
        l, r := x / d, x % d
        if i == l + r {
            fmt.Printf("%d ", i)
        }
    }
}

* Problema este adaptata de la ceva asemanator gasit pe HackerRank

Edited December 15, 2018 by Raul

TheOne01 · December 15, 2018

Nu cred ca la inceput era specificat ca cele doua jumatati sa fie egale. Oricum am inteles Multumesc !

Raul · December 15, 2018

3 hours ago, TheOne01 said:

Nu cred ca la inceput era specificat ca cele doua jumatati sa fie egale. Oricum am inteles Multumesc !

Mi-am dat seama ca nu se intelegea foarte clar treaba asta, de aceea am si modificat, acum sigur nu mai sunt dileme.

urs · December 19, 2018

import math

def isKaprekar(a):
    n = (int)(math.pow(a, 2))
    n_arr = [int(i) for i in str(n)]
    midd = 0

    # take care of the numbers lt 10:
    if a == 1:
        return True
    if n < 10:
        return False

    if n % 2 == 0:
        midd = (int)(len(n_arr) / 2)
    else:
        midd = (int)(len(n_arr) / 2)

    if( (int)(''.join(str(x) for x in n_arr[0:midd])) +
        (int)(''.join(str(x) for x in n_arr[midd :])) == a):
        return True
    else:
        return False

for i in range(0, 10001):
    # print(i)
    if isKaprekar(i):
        print(i)

PiTong

urs · December 19, 2018

Just now, urs said:


import math

def isKaprekar(a):
    n = (int)(math.pow(a, 2))
    n_arr = [int(i) for i in str(n)]
    midd = 0

    # take care of the numbers lt 10:
    if a == 1:
        return True
    if n < 10:
        return False

    if n % 2 == 0:
        midd = (int)(len(n_arr) / 2)
    else:
        midd = (int)(len(n_arr) / 2)

    if( (int)(''.join(str(x) for x in n_arr[0:midd])) +
        (int)(''.join(str(x) for x in n_arr[midd :])) == a):
        return True
    else:
        return False

for i in range(0, 10001):
    # print(i)
    if isKaprekar(i):
        print(i)

PiTong

da, stiu ca se putea mai dragut cu impartit/modulus cu puteri ale lui 10, da' astia suntem, cu astia defilam.

Raul · December 19, 2018

Testat, este in regula, a trecut toate testcase-urile, kudos!

Sign In

[Easy] Algo challenge #2

Recommended Posts

Raul

theandruala

Raul

TheOne01

theandruala

Raul

TheOne01

Raul

urs

urs

Raul

Join the conversation

Browse

Activity

Pages