Elementų su nelyginiais koeficientais skaičius nurodytame diapazone
#practiceLinkDiv { display: none !important; } Duotas diapazonas [ n m ] suraskite elementų, turinčių nelyginį skaičių faktorių nurodytame diapazone ( n ir m imtinai).
Pavyzdžiai:
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 Paprastas Sprendimas yra kilpa per visus skaičius, pradedant nuo n . Kiekvienam skaičiui patikrinkite, ar jis turi lyginį veiksnių skaičių. Jei jis turi lyginį veiksnių skaičių, padidinkite tokių skaičių skaičių ir galiausiai atspausdinkite tokių elementų skaičių. Norėdami efektyviai rasti visus natūraliojo skaičiaus daliklius, remkitės Visi natūraliojo skaičiaus dalikliai
An Efektyvus Sprendimas yra stebėti modelį. Tik tie skaičiai, kurie yra tobuli kvadratai turi nelyginį skaičių veiksnių. Panagrinėkime šį modelį per pavyzdį.
Pavyzdžiui, 9 turi nelyginį koeficientų skaičių 1 3 ir 9. 16 taip pat turi nelyginį koeficientų skaičių 1 2 4 8 16. Taip yra dėl to, kad skaičiai, išskyrus tobulus kvadratus, visi faktoriai pateikiami porų pavidalu, tačiau tobuliems kvadratams vienas veiksnys yra vienas ir bendra suma yra nelyginė.
Kaip rasti tobulų kvadratų skaičių diapazone?
Atsakymas yra skirtumas tarp kvadratinės šaknies m ir n-1 ( ne n )
Yra nedidelis įspėjimas. Kaip ir abu n ir m yra imtinai, jei n yra tobulas kvadratas, gausime atsakymą, kuris yra mažesnis nei vienas tikrasis atsakymas. Norėdami tai suprasti, apsvarstykite diapazoną [4 36]. Atsakymas yra 5, ty skaičiai 4 9 16 25 ir 36.
Bet jei padarysime (36**0.5) - (4**0.5), gausime 4. Taigi, norėdami išvengti šios semantinės klaidos, imame 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>
Išvestis:
Count is 8
Laiko sudėtingumas: O(1)
Pagalbinė erdvė: O(1)
