Aantal elementen met oneven factoren binnen een bepaald bereik
#practiceLinkDiv {weergave: geen! belangrijk; } Gegeven een bereik [ N M ] zoek het aantal elementen met een oneven aantal factoren in het gegeven bereik ( N En M inclusief).
Voorbeelden:
Input : n = 5 m = 100 Output : 8 The numbers with odd factors are 9 16 25 36 49 64 81 and 100 Input : n = 8 m = 65 Output : 6 Input : n = 10 m = 23500 Output : 150
A Eenvoudige oplossing is om alle getallen vanaf te doorlopen N . Controleer voor elk getal of het een even aantal factoren heeft. Als het een even aantal factoren heeft, verhoog dan het aantal van dergelijke getallen en druk uiteindelijk het aantal van dergelijke elementen af. Om alle delers van een natuurlijk getal efficiënt te vinden, raadpleegt u Alle delers van een natuurlijk getal
Een Efficiënte oplossing is het patroon observeren. Alleen de cijfers die dat wel zijn perfecte vierkanten een oneven aantal factoren hebben. Laten we dit patroon analyseren aan de hand van een voorbeeld.
9 heeft bijvoorbeeld een oneven aantal factoren 1 3 en 9. 16 heeft ook een oneven aantal factoren 1 2 4 8 16. De reden hiervoor is dat voor andere getallen dan perfecte kwadraten alle factoren in de vorm van paren zijn, maar voor perfecte kwadraten is één factor enkelvoudig en maakt het totaal oneven.
Hoe vind je het aantal perfecte vierkanten in een bereik?
Het antwoord is het verschil tussen de wortel van M En n-1 ( niet n )
Er is een kleine waarschuwing. Als beide N En M zijn inclusief als N een perfect kwadraat is, krijgen we een antwoord dat kleiner is dan één van het werkelijke antwoord. Om dit te begrijpen, moet u rekening houden met bereik [4 36]. Het antwoord is 5, dat wil zeggen de cijfers 4 9 16 25 en 36.
Maar als we (36**0,5) - (4**0,5) doen, krijgen we 4. Om deze semantische fout te voorkomen, nemen we dus n-1 .
// C++ program to count number of odd squares // in given range [n m] #include using namespace std ; int countOddSquares ( int n int m ) { return ( int ) pow ( m 0.5 ) - ( int ) pow ( n -1 0.5 ); } // Driver code int main () { int n = 5 m = 100 ; cout < < 'Count is ' < < countOddSquares ( n m ); return 0 ; }
Java // Java program to count number of odd squares // in given range [n m] import java.io.* ; import java.util.* ; import java.lang.* ; class GFG { public static int countOddSquares ( int n int m ) { return ( int ) Math . pow (( double ) m 0.5 ) - ( int ) Math . pow (( double ) n - 1 0.5 ); } // Driver code for above functions public static void main ( String [] args ) { int n = 5 m = 100 ; System . out . print ( 'Count is ' + countOddSquares ( n m )); } } // Mohit Gupta_OMG <(o_0)>
Python3 # Python program to count number of odd squares # in given range [n m] def countOddSquares ( n m ): return int ( m ** 0.5 ) - int (( n - 1 ) ** 0.5 ) # Driver code n = 5 m = 100 print ( 'Count is' countOddSquares ( n m )) # Mohit Gupta_OMG <0_o>
C# // C# program to count number of odd // squares in given range [n m] using System ; class GFG { // Function to count odd squares public static int countOddSquares ( int n int m ) { return ( int ) Math . Pow (( double ) m 0.5 ) - ( int ) Math . Pow (( double ) n - 1 0.5 ); } // Driver code public static void Main () { int n = 5 m = 100 ; Console . Write ( 'Count is ' + countOddSquares ( n m )); } } // This code is contributed by Nitin Mittal.
PHP // PHP program to count // number of odd squares // in given range [n m] function countOddSquares ( $n $m ) { return pow ( $m 0.5 ) - pow ( $n - 1 0.5 ); } // Driver code $n = 5 ; $m = 100 ; echo 'Count is ' countOddSquares ( $n $m ); // This code is contributed // by nitin mittal. ?>
JavaScript < script > // JavaScript program to count number of odd squares // in given range [n m] function countOddSquares ( n m ) { return Math . pow ( m 0.5 ) - Math . pow ( n - 1 0.5 ); } // Driver Code let n = 5 m = 100 ; document . write ( 'Count is ' + countOddSquares ( n m )); < /script>
Uitgang:
Count is 8
Tijdcomplexiteit: O(1)
Hulpruimte: O(1)
